题目
数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。
假设数组非空，并且一定存在满足条件的数字。
思考题：
假设要求只能使用 O(n) 的时间和额外 O(1) 的空间，该怎么做呢？
样例
输入：[1,2,1,1,3]
输出：1

解法一：快速选择

长度超过一半，意味着快速选择进行到某一轮之后，左右两部分当中一定有一部分完全一样，我们可以判断最左端或者最右端的数是否和枢轴相等，不是的话，就选择长度超过1/2的那部分继续
时间复杂度O(n)，空间复杂度O(1)

class Solution {
public:
    int moreThanHalfNum_Solution(vector<int>& nums) {
        return quick_select(nums, 0, nums.size() - 1);
    }
    int quick_select(vector<int> &nums, int l, int r) {
        if (l >= r) return nums[l];
        int idx = rand() % (r - l + 1) + l;
        int x = nums[idx];
        int i = l - 1, j = r + 1;
        while (i < j) {
            while (nums[++i] < x);
            while (nums[--j] > x);
            if (i < j) swap(nums[i], nums[j]);
        }
        if (nums[l] == x || nums[r] == x) return x;
        int delta = i - l + 1;
        if (delta > nums.size() / 2) return quick_select(nums, l, i);
        else return quick_select(nums, i + 1, r);
    }
};

解法二：众数

出现的次数超过数组长度的一半，也就意味着超过了其余所有数字出现次数的总和
时间复杂度O(n)，空间复杂度O(1)

class Solution {
public:
    int moreThanHalfNum_Solution(vector<int>& nums) {
        int cnt = 0, val = 0;
        for (auto x: nums) {
            if (x == val) cnt++;
            else {
                if (cnt) cnt--;
                else {
                    cnt = 1;
                    val = x;
                }
            }
        }
        return val;
    }
};