求众数
问题链接：https://leetcode-cn.com/problems/majority-element-ii/
一、问题描述
给定一个大小为 n 的整数数组，找出其中所有出现超过 ? n/3 ? 次的元素。
进阶：尝试设计时间复杂度为 O(n)、空间复杂度为 O(1)的算法解决此问题。
示例 1：
输入：[3,2,3]
输出：[3]
示例 2：
输入：nums = [1]
输出：[1]
示例 3：
输入：[1,1,1,3,3,2,2,2]
输出：[1,2]
提示：
1 <= nums.length <= 5 * 104
-109 <= nums[i] <= 109
二、问题分析
本题要求线性时间复杂度和常量的空间复杂度，所以就不能创建新的数据结构，接下来分析问题，本题要求找出出现次数超过 ? n/3 ?的元素（注意是超过），可以做一个假设，如果n个元素中有4个元素出现次数都超过 ? n/3 ? 那么整个数组的大小就达到了4*（? n/3 ?+1），这个值显然大于n，所以数组中不可能有四个元素出现次数超过? n/3 ?。把这个结论一般化，假设数组中有k给元素出现次数超过? n/3 ?，那么对于k应该满足：k*(? n/3 ?+1)<=n，这里加1只是为了保证这k个元素的出现次数超过? n/3 ?，把这个不等式化简就有k<=3n/(n+3)，根据题目描述，分母最小值一定是n+3；把这个不等式进行缩放有3n/(n+3)<3，所以得出k<3。
通过上述分析，我们已经得出可以满足要求的元素最大不超过两个，那么我们可以采用计票的方式统计数组中的众数。那么可以任选数据结构来实现代码，只要保证使用常量的空间就行。
摩尔投票法：该方法可以通过一次遍历找出数组中出现频率超过一半的一个众数，这个方法的思想就是“抵消”，开始遍历数组时令第一个元素为候选元素并为他计票，如果遇到相同元素，则票数加1，如果遇到不同元素则票数-1，如果票数=0，则替换候选人，虽然在遍历过程中我们可能漏记了某些候选人的票，但其实只需要把整个过程看作是“候选人”与“非候选人”之间的对抗过程即可，所有非候选人，不管是不是同一个人，他们的票都被用来抵消候选人的票，这样下来最后剩下的候选人，就是我们要找的那个。数学上也可以很直观的证明，我们设候选人的票数为x，则所有非后选人的总票数为n-x，如果x>? n/2 ?，那么x>n-x，我们找的候选人就没错
回到这个问题，我们要找至多两位候选人，那么我们依旧把候选人票和非候选人票分割开来，最后每位候选人票数一定是多于? n/3 ?，我们也可以在代码中进行相互抵消实现，遍历到最后可以得到两个可能的候选人，此时对这两个候选人进行一次计票，把不满足要求的踢掉
三、算法实现
代码：
1 class Solution { 2 public List<Integer> majorityElement(int[] nums) { 3 List<Integer> res = new ArrayList<>();//结果数组 4 if(nums.length == 0){ 5 return res; 6 } 7 int can1 = 0,can2 = 0;//can为两位竞选者 8 int f_can1 = 0,f_can2 = 0;//f_can为两位竞选者的票数 9 for(int i=0;i<nums.length;i++){//遍历数组 10 if(nums[i] == can1){ 11 f_can1++; 12 continue; 13 } 14 if(nums[i] == can2){ 15 f_can2++; 16 continue; 17 } 18 if(nums[i] != can1 && nums[i] != can2){ 19 if(f_can1==0){ 20 can1 = nums[i]; 21 f_can1++; 22 }else if(f_can2 == 0){ 23 can2 = nums[i]; 24 f_can2++; 25 }else{ 26 f_can1--; 27 f_can2--; 28 } 29 } 30 } 31 //最后需要对票数进行统计，排除不满足题意的候选人 32 f_can1=f_can2=0; 33 for(int i=0;i<nums.length;i++){ 34 if(nums[i] == can1){ 35 f_can1++; 36 }else if(nums[i] == can2){ 37 f_can2++; 38 } 39 } 40 if(f_can1>nums.length/3){ 41 res.add(can1); 42 } 43 if(f_can2>nums.length/3){ 44 res.add(can2); 45 } 46 return res; 47 } 48 }
原文：https://www.cnblogs.com/zyq79434/p/15096423.html