本文主要是介绍寻找“众数”，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

1、描述

寻找一个数组中出现最多的数字，这个数字出现的次数大于n/2

2、关键字

特殊“众数”，数组

3、思路

众数大于一半，直接位运算
我使用的是一个pair进行一轮遍历进行，统计抵消，

4、notes

忘记了但是位运算怎么写的了,
当使用i进行循环的时候，可以实现跳步

5、复杂度

时间O(N)
空间：O(1)

6、code

摩尔投票：
public:
    int majorityElement(vector<int>& nums) {
        int x = 0,votes = 0;
        for(auto num : nums){
            if(votes == 0) x = num;
            votes += num==x ? 1:-1;
        }
        return x;
    }
};

自己写的摩尔投票，兑子

class Solution {
public:
    int majorityElement(vector<int>& nums) {
        pair<int,int>res(nums[0],1);
        for(int i =1; i < nums.size(); i++){
            if(res.first == nums[i]){
                res.second++;
            }
            else{
                res.second--;
                if(res.second == 0 && i + 1 < nums.size()){
                    res.first = nums[i + 1];
                    i++;  // 因为上一句赋值了下一个元素，所以这里直接跳过这个 i+1
                    res.second = 1;
                }
            }
        }
        return res.first;

    }
};

这篇关于寻找“众数”的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！