数组中出现次数多于n/2的元素
数组中出现次数多于 n / 2 的元素
可以利用 Boyer-Moore Majority Vote Algorithm 来解决这个问题，使得时间复杂度为 O(N)。可以这么理解该算法：使用 cnt 来统计一个元素出现的次数，当遍历到的元素和统计元素不相等时，令 cnt–。如果前面查找了 i 个元素，且 cnt == 0，说明前 i 个元素没有 majority，或者有 majority，但是出现的次数少于 i / 2，因为如果多于 i / 2 的话 cnt 就一定不会为 0。此时剩下的 n - i 个元素中，majority 的数目依然多于 (n - i) / 2，因此继续查找就能找出 majority。
public int majorityElement(int[] nums) {
int cnt = 0, majority = nums[0];
for (int num : nums) {
majority = (cnt == 0) ? num : majority;
cnt = (majority == num) ? cnt + 1 : cnt - 1;
}
return majority;
}
找两个超过n/3的
思路：摩尔投票升级版，超过n/3的数最多只能有两个；
先选出两个候选人A,B,遍历数组，如果投A（等于A），则A的票数++;如果投B，B的票数++；
如果A,B都不投（即与A，B都不相等）,那么检查此时是否AB中候选人的票数是否为0，如果为0,则成为新的候选人；
如果A,B两个人的票数都不为0，那么A,B两个候选人的票数均–；
遍历结束后选出两个候选人，但是这两个候选人是否满足>n/3，还需要再遍历一遍数组，找出两个候选人的具体票数
public class Solution {
/**
* @param nums: A list of integers
* @return: The majority number that occurs more than 1/3
*/
public int majorityNumber(ArrayList<Integer> nums) {
// write your code
if (nums == null || nums.size() == 0) {
return -1;
}
int num1 = 0;
int num2 = 0;
int count1 = 0;
int count2 = 0;
for (int i = 0; i < nums.size(); i++) {
int newNum = nums.get(i);
if (count1 == 0) {
num1 = newNum;
count1++;
} else if (num1 == newNum) {
count1++;
} else if (count2 == 0) {
num2 = newNum;
count2++;
} else if (num2 == newNum) {
count2++;
} else {
count1--;
count2--;
}
}
count1 = 0;
count2 = 0;
for (int i = 0; i < nums.size(); i++) {
if (nums.get(i) == num1) {
count1++;
}
if (nums.get(i) == num2) {
count2++;
}
}
return count1 > count2 ? num1 : num2;
}
}