229.Majority Element II

Gven an integer array of size n、find all elemens that appar more than n/3_;times.The algorithm shound run inlinea time and in O(1)space.
Solution 1:Moore voting
169の考え方Solution 1と同じです。http://www.jianshu.com/p/931ed67158fe 考え方：主な考えは毎回三つの違った要素を見つけて一緒に捨てることです。最終的に残ったのは＞n/3が現れた可能性があります。せいぜい二つしかないです。n/3回のcandidatesを定義します。もしあれば、Moore votingは選択しますが、問題はguranteeがないので、countを通ってdouble checkに来なければなりません。Time Coplexity:O(N)Space Coplexity:O(1)
Solution 2：二分割で一番多く出現した二つの再チェックを見つけますか？
Solution 3:Sort
考え：sortの後で1/3のところと2/3のところのこの2つのcandidatesを探し当てます。もっとdouble checkはn/3回を超えていますか？checkの方式はすでに順序を並べていますので、binary searchは開始位置と終了位置を探してもいいです。checkは81題に類似しています。http://www.jianshu.com/p/597d80b0c161 Solution 3 refer:https://discuss.leetcode.com/topic/65330/a-binary-search-solution-assuming-the-input-array-is-sorted-beats-99/2
コード：not finished
Solution 4:hashmap
Solution 1 Code:

class Solution1 {
    // Moore voting algorithm
    public List majorityElement(int[] nums) {
        
        List result = new ArrayList();
        
        int candidate1 = 0, candidate2 = 0; // there are max two candidates
        int count1 = 0, count2 = 0;
        for(int i = 0; i < nums.length; i++) {
            if(nums[i] == candidate1) {
                count1++;
            } else if (nums[i] == candidate2) {
                count2++;
            } else if(count1 == 0) {
                candidate1 = nums[i];
                count1 = 1;
            } else if(count2 == 0) {
                candidate2 = nums[i];
                count2 = 1;
            } else {
                count1--;
                count2--;
            }
        }
        
        // check two candidiates, since there is no guarantee there are two that appear > n / 3
        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;
    }
        
}