Problem:
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.
Thinking:
这道题和LintCode的Majority Number II很像,但是稍有不同,需要考虑一个特殊情况:
Input:
[1,2]
Expected:
[1,2]
When there are two different elements in the array, both of the two elements appear more than n/3 times.
Java Code (写得这么长T_T):
public class Solution {
public List<Integer> majorityElement(int[] nums) {
List<Integer> result = new ArrayList<Integer>();
if (nums == null || nums.length == 0) {
return result;
}
int candidate1 = 0;
int candidate2 = 0;
int count1 = 0;
int count2 = 0;
for (int i = 0; i < nums.length; i++) {
if (count1 == 0) {
candidate1 = nums[i];
} else if (count2 == 0) {
candidate2 = nums[i];
}
if (nums[i] == candidate1) {
count1++;
}
else if (nums[i] == candidate2) {
count2++;
} else {
count1--;
count2--;
}
}
count1 = 0;
count2 = 0;
for (int i = 0; i < nums.length; i++) {
if (nums[i] == candidate1) {
count1++;
}else if (nums[i] == candidate2) {
count2++;
}
}
if (count1 > nums.length / 3) {
result.add(candidate1);
}
if (count2 > nums.length / 3) {
result.add(candidate2);
}
return result;
}
}
这道题是怎么想到这个思路的?我拿到这个问题,我会首先想是否可以将原来的数组拆成两部分,但是没有找到方法。
回复删除虽然代码可以AC,但是我不明白为什么能够AC
思路大概是,要找的是出现次数大于 n/3 的数,所以这份代码里面维护四个变量,分别是 candidate1 和它对应的次数 count1,candidate2 和它对应的次数 count2,一遍遍历,最后剩下的两个 candidate 一定是出现次数超过 n/3 的。然后用第二遍遍历做验证(如果不做的话,在 Input:[1] 这类 test case 就会出错)
删除