題目
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.
題目很簡(jiǎn)短，給定一個(gè)包含n個(gè)數(shù)字的數(shù)組绘证，找出所有出現(xiàn)次數(shù)超過 ? n/3 ? 次的數(shù)。要求O(n)時(shí)間復(fù)雜度和O(1)空間復(fù)雜度嚷那。
解析
- 因?yàn)橐蟪^ ? n/3 ? 次，所以最多只有兩個(gè)數(shù)
- 可以參考找出出現(xiàn)次數(shù)大于一半容量的數(shù)的解法：majority-vote-algorithm
- 根據(jù)以上兩點(diǎn)魏宽，可以設(shè)兩個(gè)變量腐泻，兩個(gè)計(jì)數(shù)變量队询，利用投票算法，得到最后的候選數(shù)蚌斩，為什么是候選數(shù)呢铆惑，因?yàn)閿?shù)組并未保證一定有這種數(shù)和數(shù)量送膳。所以還需要再一次遍歷檢查候選數(shù)是否符合要求。
復(fù)雜度分析
兩次遍歷數(shù)組叠聋，時(shí)間復(fù)雜度為O(n)，空間復(fù)雜度為O(1)
代碼
public List<Integer> majorityElement(int[] nums) {
List<Integer> res = new ArrayList();
if(nums == null || nums.length == 0) return res;
int candidate1 = 0, candicate2 = 1; //隨便賦值就可以
int cnt1 = 0, cnt2 = 0;
for(int num : nums){
if(num == candidate1){
cnt1 ++;
}else if(num == candicate2){
cnt2 ++;
}else if(cnt1 == 0){
cnt1 ++;
candidate1 = num;
}else if(cnt2 == 0){
cnt2 ++;
candicate2 = num;
}else{
cnt1 --;
cnt2 --;
}
}
cnt1 = cnt2 = 0;
for(int num: nums){
if(num == candidate1){
cnt1 ++;
}else if(num == candicate2){
cnt2 ++;
}
}
if(cnt1 > nums.length / 3){
res.add(candidate1);
}
if(cnt2 > nums.length / 3){
res.add(candicate2);
}
return res;
}