169.Majority Element

Description

	#169	Majority Element	Easy
		Array	Top 150
Given an array nums of size n, return the majority element..

The majority element is the element that appears more than ⌊n / 2⌋ times. You may assume that the majority element always exists in the array.

Example 1:

Input: nums = [3,2,3]
Output: 3

Example 2:

Input: nums = [2,2,1,1,1,2,2]
Output: 2

HashMap

Runtime 12ms		Memory 49.68MB

class Solution {
    public int majorityElement(int[] nums) {
        Map<Integer, Integer> counts = new HashMap<>();
        float half = nums.length / 2.0f;
        for(int i = 0; i < nums.length; i++) {
            int count = counts.getOrDefault(nums[i], 0) + 1;
            if(count > half) return nums[i];
            counts.put(nums[i], count);
        }
        throw new RuntimeException("No majority element found");
    }
}

Sort and return middle

The element must be at n/2 after sorted!

Runtime 5ms		Memory 53.59MB

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

Bit Manipulation

For each number, if it's the majority, then each bit must also be the majority!

5 5 2 1 2 2 2 =>
1 0 1
1 0 1
0 1 0
0 0 1 
0 1 0
0 1 0
0 1 0

Runtime 6ms		Memory 52.97MB

class Solution {
    public int majorityElement(int[] nums) {
        int n = nums.length, ans = 0;
        int half = n / 2;
        for(int i = 0; i < 32; i++) {
            int count = 0, mask = 1 << i;
            for(int j = 0; j < n; j++) {
                if((nums[j]  & mask) == mask)
                    count ++;
            }
            if(count > half) ans |= 1 << i;
        }
        return ans;
    }
}

Boyer-Moore Majority Vote Algorithm

Runtime 1ms		Memory 53.97MB

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