Problem_Majority Element I, II - xwu36/LeetCode GitHub Wiki

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.

1.  Initialize index and count of majority element
     maj_index = 0, count = 1

2.  Loop for i = 1 to size – 1
    (a) If a[maj_index] == a[i]
          count++  (b) Else
        count--;(c) If count == 0
          maj_index = i;
          count = 1
3.  Return a[maj_index]

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

We can tackle this problem as single number II,
for one bit, if it is 1 in majority number, we will have more 1s than 0s, if it is 0 in majority, we will have less 1s.

class Solution {
    public int majorityElement(int[] nums) {
        int n = nums.length;
        if(n == 0) return 0;
        int res = 0;
        for(int i = 0; i < 32; i++){
            int one = 0;
            for(int num : nums){
                if(((num >> i) & 1) != 0)
                    one++;
            }
            if(one * 2 > n)
                res |= (1 << i);      
        }
        return res;
    }
}

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 List<Integer> majorityElement(int[] nums) {
    List<Integer> res = new ArrayList<>();
    int count1 = 0, count2 = 0, candidate1 = 0, candidate2 = -1;
    for(int n : nums){
        if(n == candidate1) count1++;
        else if(n == candidate2) count2++;
        else if (count1 == 0){
            candidate1 = n;
            count1 = 1;
        }else if (count2 == 0){
            candidate2 = n;
            count2 = 1;
        }else {
            count1--;
            count2--;
        }
    }
    count1 = 0;
    count2 = 0;
    for(int n : nums){
        if(candidate1 == n) count1++;
        if(candidate2 == n) count2++;
    }
    if(count1 > nums.length / 3)
        res.add(candidate1);
    if(count2 > nums.length / 3)
        res.add(candidate2);
    return res;
}