Majority Element I

Given an array of size n, find the majority element. The majority element is the element that appears more than ? n/2 ? times.

You may assume that the array is non-empty and the majority element always exist in the array.

排序法

思路

將數(shù)組排序，這時候數(shù)組最中間的數(shù)肯定是眾數(shù)。

public class Solution1 {
    public int majorityElement(int[] nums) {
        Arrays.sort(nums);
        return nums[nums.length / 2];
    }
}

投票法

思路

記錄一個elem變量，還有一個count變量，開始遍歷數(shù)組。如果新數(shù)和elem一樣，那么count加上1，否則的話，如果count不是0，則count減去1，如果count已經(jīng)是0，則將candidate更新為這個新的數(shù)。因為每一對不一樣的數(shù)都會互相消去，最后留下來的elem就是眾數(shù)。

public class Solution2 {
    public int majorityElement(int[] nums) {
        int elem=0;
        int count=0;
        for (int i=0;i<nums.length;i++){
            if (count==0){
                elem=nums[i];
                count=1;
            }else {
                if (elem==nums[i])
                    count++;
                else 
                    count--;
            }
        }
        return elem;
    }
}

Majority Element II

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.

投票法

上一題中，超過一半的數(shù)只可能有一個，所以我們只要投票出一個數(shù)就行了。而這題中，超過n/3的數(shù)最多可能有兩個，所以我們要記錄出現(xiàn)最多的兩個數(shù)。同樣的兩個elem和對應(yīng)的兩個count，如果遍歷時，某個候選數(shù)和到當(dāng)前數(shù)相等，則給相應(yīng)計數(shù)器加1。如果兩個計數(shù)器都不為0，則兩個計數(shù)器都被抵消掉1。如果某個計數(shù)器為0了，則將當(dāng)前數(shù)替換相應(yīng)的候選數(shù)，并將計數(shù)器初始化為1。最后我們還要遍歷一遍數(shù)組，確定這兩個出現(xiàn)最多的數(shù)，是否都是眾數(shù)。

public class Solution {
    public List<Integer> majorityElement(int[] nums) {
        List<Integer> result=new LinkedList<>();
        if(nums==null||nums.length==0)return result;
        int elem1=0,count1=0,elem2=0,count2=0;
        for(int i=0;i<nums.length;i++){
            if(nums[i]==elem1){
                count1++;
            }else if(nums[i]==elem2){
                count2++;
            }else if(count1!=0&&count2!=0){
                count1--;
                count2--;
            }else{
                if(count1==0){
                    elem1=nums[i];
                    count1=1;
                }else{
                    elem2=nums[i];
                    count2=1;
                }
            }
        }
        //上面只是計算出最多的兩個數(shù)，接下來計算出出現(xiàn)的次數(shù)是否超過n/3
        count1=0;
        count2=0;
        for(int i=0;i<nums.length;i++){
            if(nums[i]==elem1)count1++;
            else if(nums[i]==elem2)count2++;
        }
        if(count1>nums.length/3)result.add(elem1);
        if(count2>nums.length/3)result.add(elem2);
        return result;
    }
}