Given an integer array of size n, find all elements that appear more than ⌊ n/3 ⌋ times.
Note: The algorithm should run in linear time and in O(1) space.
这是leetcode求众数的一个算法题（https://leetcode.com/problems/majority-element-ii/），在解决这道题之前，需要了解摩尔投票算法（https://gregable.com/2013/10/majority-vote-algorithm-find-majority.html）。
问题描述：
假设有一个没有排序的列表，想求出超过列表元素一半的那个元素，那么这个值是哪个呢？如果没有，则需知道没有这个众数，你需要尽可能完成这道题。
出现此问题的一个常见原因可能是容错计算，执行多个冗余计算, 然后验证大多数结果是否一致。
简单方案：
列表排好序，如果存在这个元素，那么它一定在列表的中间，为了确认它是众数，需要再次遍历列表并记录词频。 时间复杂度是0(nlogn)
摩尔投票算法：
时间复杂度为O(n) 空间复杂度O(1)
只需遍历2次列表，实现也很简单, 尽管了解它是如何工作的有点棘手。
在第一个过程中, 我们生成一个候选值, 如果有多数, 则为多数值。第二个传递只是计算该值的频率并确认。
在第一个过程中，我们需要两个值：
1 一个候选值candidate，初始化为任意值
2 一个计数count，初始化为0
遍历列表中的每个元素，我们首先要检查count值，如果count为0，则将candidate设置为当前元素值，接下来 比较列表中的元素值和candidate，如果是同一个候选值，则count++，否则count--。
puthon 代码段：
candidate = 0
count = 0
for value in input:
if count == 0:
candidate = value
if candidate == value:
count += 1
else:
count -= 1
在所有输入的末尾,如果存在众数，则就是candidate的值，接下来花费O(n)的时间复杂度确认candidate就是众数。
实现代码：
public List<Integer> majorityElement(int[] nums) {
if (null == nums || nums.length ==0) {
return new LinkedList<>();
}
int candidateA = 0, candidateB = 1;
int countA = 0, countB = 0;
for (int num : nums) {
if (num == candidateA) {
countA++;
continue;
}
if (num == candidateB) {
countB++;
continue;
}
if (countA == 0) {
candidateA = num;
countA++;
continue;
}
if (countB == 0) {
candidateB = num;
countB++;
continue;
}
countA--;
countB--;
}
countA = 0;
countB = 0;
for (int num : nums) {
if (num == candidateA) {
countA++;
} else if (num == candidateB) {
countB++;
}
}
List<Integer> list = new LinkedList<>();
if (countA > nums.length / 3) {
list.add(candidateA);
}
if (countB > nums.length / 3) {
list.add(candidateB);
}
return list;
}
网友评论