Leetcode169. 多数元素(HOT100)

链接

我写的代码：

class Solution {
public:
    int majorityElement(vector<int>& nums) {
        if(nums.size()==1)return nums[0];
        sort(nums.begin(),nums.end());
        int n = nums.size();
        int res = 0;
        for(int i = 0;i<n;i++){
            int j = i;
            while(j+1<n&&nums[j]==nums[j+1])++j;
            if((i!=j)&&(j-i+1)>n/2){
                res = nums[j];
                break;
            }
        }
        return res;
    }
};

我模仿的优秀的代码：

class Solution {
public:
    int majorityElement(vector<int>& nums) {
        int r,t = 0;
        for(const auto&e:nums){
            if(t==0){
                r = e;
                ++t;
            }
            else{
                if(r==e){
                    ++t;
                }
                else{
                    --t;
                }
            }
        }
        return r;
    }
};

优秀的代码本身：

class Solution {
public:
    int majorityElement(vector<int>& nums) {
        int r,c = 0;
        for(auto x:nums){
            if(!c)r = x,c = 1;
            else if(r==x)++c;
            else --c;
        }
        return r;
    }
};

用 r 记录一个数，t 记录一个次数，遍历这个数组，如果遇到了和 r 相同的值，++t；说明 r 又多了一个，遇到了不同的数，就--t ；说明 r 被抵消了一个，而当t 减到0的时候，我们就用当前遍历到的元素当作新的r 。

为什么可以这样做呢？因为题目中说了：存在一个元素出现次数大于n/2 ;

我们选择一个数当作r 也就是答案，存在两种可能：1）这就是真正的答案2）这是假的答案，真正的r 我们没有找到。

那么我们继续遍历即可，如果它是真正的答案，那么遍历完所有元素，它肯定还是r 没变，因为他出现的次数超过了数组的一半，

如果他不是真正的答案，那么它会因为数量不足而被数量超过数组一半的真正的答案代替掉。