输入：[3,2,3]
输出：3

输入：[2,2,1,1,1,2,2]
输出：2

 class="hljs-ln-numbers"> class="hljs-ln-line hljs-ln-n" data-line-number="1">

 解法二： 哈希

时间复杂度O(N)，空间复杂度O(N)

统计每个数字出现的次数，输出出现超过半数的数字。

遇到这种数值计数类的题目，第一反应是桶排序的思想，因为可以很方便的做到O（N)。

但是单纯的桶排序需要根据数值大开一块连续的数组，非常消耗内存，对于相对较散的数值排列，就可以用到哈希来进行散列存储，节省空间。
常见的数据结构是「哈希表」，C++中可以使用 unordered_map。

 class="hljs-ln-numbers"> class="hljs-ln-line hljs-ln-n" data-line-number="1"> class="hljs-ln-code"> class="hljs-ln-line">class Solution {
 class="hljs-ln-numbers"> class="hljs-ln-line hljs-ln-n" data-line-number="2"> class="hljs-ln-code"> class="hljs-ln-line">public:
 class="hljs-ln-numbers"> class="hljs-ln-line hljs-ln-n" data-line-number="3"> class="hljs-ln-code"> class="hljs-ln-line">    int majorityElement(vector<int>& nums) {
 class="hljs-ln-numbers"> class="hljs-ln-line hljs-ln-n" data-line-number="4"> class="hljs-ln-code"> class="hljs-ln-line">        unordered_map <int, int> mostNum;
 class="hljs-ln-numbers"> class="hljs-ln-line hljs-ln-n" data-line-number="5"> class="hljs-ln-code"> class="hljs-ln-line">        for(int a:nums){
 class="hljs-ln-numbers"> class="hljs-ln-line hljs-ln-n" data-line-number="6"> class="hljs-ln-code"> class="hljs-ln-line">            if(++mostNum[a] > nums.size()/2) return a;
 class="hljs-ln-numbers"> class="hljs-ln-line hljs-ln-n" data-line-number="7"> class="hljs-ln-code"> class="hljs-ln-line">        }
 class="hljs-ln-numbers"> class="hljs-ln-line hljs-ln-n" data-line-number="8"> class="hljs-ln-code"> class="hljs-ln-line">        return -1;//if there is no the number, return -1
 class="hljs-ln-numbers"> class="hljs-ln-line hljs-ln-n" data-line-number="9"> class="hljs-ln-code"> class="hljs-ln-line">    }
 class="hljs-ln-numbers"> class="hljs-ln-line hljs-ln-n" data-line-number="10"> class="hljs-ln-code"> class="hljs-ln-line">}; class="hljs-button signin" data-title="登录后复制" data-report-click="{"spm":"1001.2101.3001.4334"}" onclick="hljs.signin(event)">

解法三： 摩尔投票算法（进阶）

时间复杂度O(N)，空间复杂度O(1)

之后我想到，多数元素有一点特殊的性质是其出现次数 大于 ⌊ n/2 ⌋ ，那么我们能否从这点特殊性入手。

答案是肯定的，而且大有可为。

首先如果一个数X是多数元素，那么其在数组中X的出现次数要大于其他所有数的出现次数之和，这里把其他数统称为Y。  那么其实我们就可以从头设置一个基准数，如果这个数和后面的数相同，那么就count + 1，如果不相同那就 count - 1，当count = 0的时候，就更换基准数。

换一种表述方式，就是把两个不同的数两两组合并且去除，那么剩下的那个数肯定就是多数元素！

如下图所示： 

 后来整理之后才知道，这种思想叫做摩尔投票算法，这样做就可以达到时间复杂度O(N)，空间复杂度O(1)，也是题目中的进阶做法，这种解法和求最大连续子序列和里的在线处理算法有点相似，不得不感叹前人的智慧。

（另外说明一下，因为本方法前提条件是有多数元素存在，所以最后剩下的那个基准值肯定就是多数元素，并且题目中的意思也是测试样例中都有多数元素。但如果有不存在多数元素的情况，那就要在最后加一个判断，将整个数组过一遍和最后的基准值进行比较，看是否  > (n/2)，大于才成立。）

 class="hljs-ln-numbers"> class="hljs-ln-line hljs-ln-n" data-line-number="1"> class="hljs-ln-code"> class="hljs-ln-line">class Solution {
 class="hljs-ln-numbers"> class="hljs-ln-line hljs-ln-n" data-line-number="2"> class="hljs-ln-code"> class="hljs-ln-line">public:
 class="hljs-ln-numbers"> class="hljs-ln-line hljs-ln-n" data-line-number="3"> class="hljs-ln-code"> class="hljs-ln-line">    int majorityElement(vector<int>& nums) {
 class="hljs-ln-numbers"> class="hljs-ln-line hljs-ln-n" data-line-number="4"> class="hljs-ln-code"> class="hljs-ln-line">        int x , count = 0;
 class="hljs-ln-numbers"> class="hljs-ln-line hljs-ln-n" data-line-number="5"> class="hljs-ln-code"> class="hljs-ln-line">        for(int n:nums){
 class="hljs-ln-numbers"> class="hljs-ln-line hljs-ln-n" data-line-number="6"> class="hljs-ln-code"> class="hljs-ln-line">            if(count == 0) x = n, count = 0;
 class="hljs-ln-numbers"> class="hljs-ln-line hljs-ln-n" data-line-number="7"> class="hljs-ln-code"> class="hljs-ln-line">            if(n == x) count++;
 class="hljs-ln-numbers"> class="hljs-ln-line hljs-ln-n" data-line-number="8"> class="hljs-ln-code"> class="hljs-ln-line">            else count--;
 class="hljs-ln-numbers"> class="hljs-ln-line hljs-ln-n" data-line-number="9"> class="hljs-ln-code"> class="hljs-ln-line">        }
 class="hljs-ln-numbers"> class="hljs-ln-line hljs-ln-n" data-line-number="10"> class="hljs-ln-code"> class="hljs-ln-line">        return x;
 class="hljs-ln-numbers"> class="hljs-ln-line hljs-ln-n" data-line-number="11"> class="hljs-ln-code"> class="hljs-ln-line">    }
 class="hljs-ln-numbers"> class="hljs-ln-line hljs-ln-n" data-line-number="12"> class="hljs-ln-code"> class="hljs-ln-line">}; class="hljs-button signin" data-title="登录后复制" data-report-click="{"spm":"1001.2101.3001.4334"}" onclick="hljs.signin(event)">

 上一篇： 从B站 (哔哩哔哩) 泄露的源码里发现了B站视频推荐的秘密

下一篇： 400+条实用C/C++框架、库、工具整理 ，你能想到的都在这里了

如果有什么要补充的，欢迎下方👇评论区留言~

1份赞许 = 100分的认可，如果感觉还不错，点个赞👍 支持一下吧 ~

不定期分享 有趣、有料、有营养内容，欢迎 订阅关注 🤝 我的博客 ，期待在这与你相遇 ~

发表评论

登录后才能发表评论和回复 注册

/ 登录

提交评论

评论记录：

未查询到任何数据！

回复评论：

×

关闭 提交评论