Question
Given an integer array of size n, find all elements that appear more than ⌊ n/3 ⌋ times. The algorithm should run in linear time and in O(1) space.
A Linear Time Voting Algorithm
Solution 1 -- Binary Search
我们发现一个规律。如果是大于 1/k 的majority，排好序的数组中，它们可能出现的位置是
len / k, len * 2/ k, len * 3 / k, ...
所以我们可以依次用二分查找法查找在 len * i / k 的各个点的start和end position，然后算长度，判断是否满足条件。
动态一些的方法是下一个待判断点的坐标为 prevEnd + len / k + 1
如图，绿线为start point 红线为end point
Time complexity O(n log n), space O(1)
public class Solution {
public List<Integer> majorityElement(int[] nums) {
Arrays.sort(nums);
List<Integer> result = new ArrayList<Integer>();
int len = nums.length;
if (len < 1)
return result;
int candidate1 = nums[len / 3];
// Find start and end of candidate1
int[] range1 = searchRange(nums, candidate1);
int num1 = range1[1] - range1[0] + 1;
if (num1 > len / 3)
result.add(candidate1);
// Find start and end of candidate2
int index = len / 3 + range1[1] + 1;
if (index >= len)
return result;
int candidate2 = nums[index];
int[] range2 = searchRange(nums, candidate2);
int num2 = range2[1] - range2[0] + 1;
if (num2 > len / 3 && candidate2 != candidate1)
result.add(candidate2);
return result;
}
private int[] searchRange(int[] nums, int target) {
int start = 0, end = nums.length - 1, mid;
int[] result = new int[2];
result[0] = -1;
result[1] = -1;
while (start + 1 < end) {
mid = (end - start) / 2 + start;
if (nums[mid] >= target)
end = mid;
else
start = mid;
}
if (nums[start] == target)
result[0] = start;
else if (nums[end] == target)
result[0] = end;
start = 0;
end = nums.length - 1;
while (start + 1 < end) {
mid = (end - start) / 2 + start;
if (nums[mid] > target)
end = mid;
else
start = mid;
}
if (nums[end] == target)
result[1] = end;
else if (nums[start] == target)
result[1] = start;
return result;
}
}Solution 2 -- Moore Voting Algorithm
Time complexity O(n), space cost O(1)
public class Solution {
public List<Integer> majorityElement(int[] nums) {
int count1 = 0, count2 = 0;
Integer num1 = null, num2 = null;
int len = nums.length;
for (int current : nums) {
if (num1 != null && current == num1.intValue()) {
count1++;
} else if (num2 != null && current == num2.intValue()) {
count2++;
} else if (num1 == null || count1 == 0) {
num1 = current;
count1 = 1;
} else if (num2 == null || count2 == 0) {
num2 = current;
count2 = 1;
} else {
count1--;
count2--;
}
}
// Check whether num1, num2, num3 are valid
count1 = 0;
count2 = 0;
for (int current : nums) {
if (current == num1.intValue()) {
count1++;
} else if (current == num2.intValue()) {
count2++;
}
}
List<Integer> result = new ArrayList<Integer>();
if (count1 > len / 3) {
result.add(num1);
}
if (count2 > len / 3) {
result.add(num2);
}
return result;
}
}