题目链接
LeetCode 面试题39. 数组中出现次数超过一半的数字[1]
题目描述
数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。
你可以假设数组是非空的，并且给定的数组总是存在多数元素。
说明：
- 1 <= 数组长度 <= 50000
示例1
输入：[1, 2, 3, 2, 2, 2, 5, 4, 2]输出:2
题解
哈希表
这个方法最简单，用哈希表记录每个数字出现的次数，最后看哪个数字次数超过一半就行了。
排序
对数组从小到大进行排序，那么众数一定在 nums[n/2] 处。为什么呢？
因为排序后相同的数都连续了，所以众数最左端的极限情况就是从下标 0 开始往后排，那么因为超过了一半，所以尾部下标一定会超过 n/2 。而最右端的极限情况就是从下标 n-1 往前排，因为超过了一半，所以头部下标也会在 n/2 之前。
综上，众数所在的区间一定会包含下标 n/2 。
随机采样
其实我第一个想到的方法反而是这个反常规的随机采样方法。因为众数超过了一半，所以采样大概率会采到这个众数。
那么我们随机采样一个数，然后遍历一遍数组看它的个数。如果个数超过了一半就是它了，否则继续采样，直到采到众数。
分治
如果把区间 [0, n-1] 平均分成两半，那么我们可以证明，原来的众数在某一半区间里依然是众数。
为什么呢？反证法，假设两半区间的众数都不是原来的众数，那么在左半区间原来的众数一定小于一半，右半区间也是的。加起来之后总数一定小于一半的，和条件是矛盾的。
所以我们递归求解两半区间的众数，然后看哪个数出现次数较多，众数就是它了。
摩尔投票
这个方法我一开始也想到了，但是没有想到这竟然有理论解释，而且是大名鼎鼎的摩尔投票算法。
它的主要步骤是这样的：
- 初始化两个变量，
cand表示候选人，cnt表示赞同它的票数。 - 如果
cnt = 0，那么cand就设置为当前的数字。 - 如果
cand等于当前数字，那么票数cnt加一，否则票数减一。 - 最后
cand就是得票超过一半的众数。
严格证明比较复杂，是一篇论文，这里说个比较好理解的思路：
- 如果当前候选人是众数，那么其他的众数会支持自己，其他的数反对自己。但是因为众数超过了一半，所以众数最后一定会当选。
- 如果当前候选人不是众数，那么就惨了，其他的数和众数全都会反对他。那反对票远远超过一半了，肯定会下台，然后换候选人。
- 上面两种情况会在
cnt = 0的时刻进行转换，也就是换候选人。
代码
哈希表（c++）
classSolution { public: intmajorityElement(vector<int>&nums) { intn=nums.size(); unordered_map<int, int>mp; for (autox : nums) mp[x]++; for (auto [k, v] : mp) { if (v>n/2) returnk; } return-1; } };
排序（c++）
classSolution { public: intmajorityElement(vector<int>&nums) { intn=nums.size(); sort(nums.begin(), nums.end()); returnnums[n/2]; } };
随机采样（c++）
classSolution { public: intmajorityElement(vector<int>&nums) { intn=nums.size(); while (1) { intidx=rand() %n; intcnt=0; for (autox : nums) { if (x==nums[idx]) cnt++; } if (cnt>n/2) returnnums[idx]; } return-1; } };
分治（c++）
classSolution { public: intnumCount(vector<int>&nums, intx, intl, intr) { intcnt=0; for (inti=l; i<=r; ++i) { if (nums[i] ==x) cnt++; } returncnt; } intfindMajority(vector<int>&nums, intl, intr) { if (l==r) returnnums[l]; intm=l+(r-l)/2; intml=findMajority(nums, l, m); intmr=findMajority(nums, m+1, r); if (ml==mr) returnml; intcl=numCount(nums, ml, l, r); intcr=numCount(nums, mr, l, r); returncl<cr?mr : ml; } intmajorityElement(vector<int>&nums) { intn=nums.size(); returnfindMajority(nums, 0, n-1); } };
摩尔投票（c++）
classSolution { public: intmajorityElement(vector<int>&nums) { intcand=0, cnt=0; for (autox : nums) { if (!cnt) cand=x; if (x==cand) cnt++; elsecnt--; } returncand; } };
哈希表（python）
classSolution: defmajorityElement(self, nums): counts=collections.Counter(nums) returnmax(counts.keys(), key=counts.get)
排序（python）
classSolution: defmajorityElement(self, nums): nums.sort() returnnums[len(nums)//2]
随机采样（python）
importrandomclassSolution: defmajorityElement(self, nums): majority_count=len(nums)//2whileTrue: candidate=random.choice(nums) ifsum(1foreleminnumsifelem==candidate) >majority_count: returncandidate
分治（python）
classSolution: defmajorityElement(self, nums, lo=0, hi=None): defmajority_element_rec(lo, hi): iflo==hi: returnnums[lo] mid= (hi-lo)//2+loleft=majority_element_rec(lo, mid) right=majority_element_rec(mid+1, hi) ifleft==right: returnleftleft_count=sum(1foriinrange(lo, hi+1) ifnums[i] ==left) right_count=sum(1foriinrange(lo, hi+1) ifnums[i] ==right) returnleftifleft_count>right_countelserightreturnmajority_element_rec(0, len(nums)-1)
摩尔投票（python）
classSolution: defmajorityElement(self, nums): count=0candidate=Nonefornuminnums: ifcount==0: candidate=numcount+= (1ifnum==candidateelse-1) returncandidate
关注【算法码上来】，每日算法干货马上就来！
参考资料
[1]
LeetCode 面试题39. 数组中出现次数超过一半的数字: https://leetcode-cn.com/problems/shu-zu-zhong-chu-xian-ci-shu-chao-guo-yi-ban-de-shu-zi-lcof/
作者简介：godweiyang，知乎同名，华东师范大学计算机系硕士在读，方向自然语言处理与深度学习。喜欢与人分享技术与知识，期待与你的进一步交流~
