数组中出现次数超过一半的数字

数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。

思路：

数组中有一个数出现的次数超过数组长度的一半，设这个数为a，其他数为b、c、d...。设time[x]表示x出现的次数，则time[a] > time[b]+time[c]+time[d]+...。time[a]-(time[b]+time[c]+time[d]+...) > 0。time[a]-time[b]-time[c]-time[d]-... > 0。从左往右遍历数组，用一个变量表示当前数cur，一个变量表示当前数出现的次数time。当数组中出现和cur相同的数时，time加一，不同时，time减一。遍历完数组后，cur就是答案

代码：

class Solution {
public:
    int majorityElement(vector<int>& nums) {
        int length = nums.size();
        if(length == 0) {
            return 0;
        }
        int cur = nums[0];
        int time = 1;
        for(int i = 1;i < length;i++) {
            if(nums[i] == cur) {
                time++;
            }
            else if(--time < 0) {
                cur = nums[i];
                time = 1;
            }
        }
        return cur;
    }
};