題目

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.

題目很簡短，給定一個(gè)包含n個(gè)數(shù)字的數(shù)組，找出所有出現(xiàn)次數(shù)超過 ? n/3 ? 次的數(shù)。要求O(n)時(shí)間復(fù)雜度和O(1)空間復(fù)雜度。

解析

1. 因?yàn)橐蟪^ ? n/3 ? 次，所以最多只有兩個(gè)數(shù)
2. 可以參考找出出現(xiàn)次數(shù)大于一半容量的數(shù)的解法：majority-vote-algorithm
3. 根據(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;
}