Majority Element(169)

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.

Credits:
Special thanks to @ts for adding this problem and creating all test cases.

Subscribe to see which companies asked this question.

Show Tags

Show Similar Problems

思路：摩尔投票算法

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

Majority Element II（229）

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.

Subscribe to see which companies asked this question.

public class Solution {
    public List<Integer> majorityElement(int[] nums) {
        if (nums == null || nums.length == 0)
            return new ArrayList<Integer>();
        int x=nums[0];
        int y=nums[0];
        int cx=0;
        int cy=0;
        for(int i=0;i<nums.length;i++){
            if(nums[i]==x){
                cx++;
            }else if(nums[i]==y){
                cy++;
            }else if(cx==0){
                x=nums[i];
                cx++;
            }else if(cy==0){
                y=nums[i];
                cy++;
            }else{
                cx--;cy--;
            }
        }
        cx=0;cy=0;
        for(int i=0;i<nums.length;i++){
            if(nums[i]==x){
                cx++;
                //为了避免x==y 那么就重复计数。
                continue;
            }
            else if(nums[i]==y)
                cy++;
        }
        List<Integer> list=new ArrayList<Integer>();
        if(cx>nums.length/3)
            list.add(x);
        if(cy>nums.length/3)
            list.add(y);
        return list;
        
    }
}

you can just use an array if it is a n/k question. it will be something like this...

public class Solution {
    public List<Integer> majorityElement(int[] nums) {
        int n = nums.length, k = 3;  //in this question, k=3 specifically
        List<Integer> result = new ArrayList<Integer>();
        if (n==0 || k<2) return result;
        int[] candidates = new int[k-1];
        int[] counts = new int[k-1];
        for (int num: nums) {
            boolean settled = false;
            for (int i=0; i<k-1; i++) {
                if (candidates[i]==num) {
                    counts[i]++;
                    settled = true;
                    break;
                } 
            }
            if (settled) continue;
            for (int i=0; i<k-1; i++) {
                if (counts[i]==0) {
                    counts[i] = 1;
                    candidates[i] = num;
                    settled = true;
                    break;
                } 
            }
            if (settled) continue;
            for (int i=0; i<k-1; i++) counts[i] = (counts[i] > 0) ? (counts[i]-1) : 0;
        }
        Arrays.fill(counts, 0);
        for (int num: nums) {
            for (int i=0;i<k-1; i++) {
                if (candidates[i]==num) {
                    counts[i]++;
                    break;
                }
            }
        }
        for (int i=0; i<k-1; i++) if (counts[i]>n/k) result.add(candidates[i]);
        return result;
    }
}