Majority Element

lc169

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.

Voting algorithms

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

lc 229 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.

public class Solution {
    public List<Integer> majorityElement(int[] nums) {
        List<Integer> res = new ArrayList<Integer>();
        if(nums == null || nums.length == 0) return res;
        int num1 = nums[0];
        int num2 = nums[0];
        int count1 = 0;
        int count2 = 0;
        for(int i = 0; i < nums.length; i++){
            if(num1 == nums[i]){
                count1++;
            }else if(num2 == nums[i]){
                count2++;
            }else if(count1 == 0){
                num1 = nums[i];
                count1 = 1;
            }else if(count2 == 0){
                num2 = nums[i];
                count2 = 1;
            } else {
                count2--;
                count1--;
            }                  
        }
        count1 =0;
        count2 =0;
        for(int i = 0; i < nums.length; i++){
            if(nums[i] == num1){
                count1++;
            }else if(nums[i] == num2){
                count2++;
            }
        }

        if(count1 > nums.length / 3) res.add(num1);
        if(count2 > nums.length / 3) res.add(num2);
        return res;

    }
}