Woodstock Blog

a tech blog for general algorithmic interview questions

[LeetCode 169] Majority Element

Question

link

Solution

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.

Show Tags
Divide and Conquer Array Bit Manipulation

Analysis

I have already covered this question in [LintCode] Majority Number. However, I have also discovered a few other very interesting solution. Check below.

Solution

The best solution is of course the voting algorithm. Read code below.

Second solution presented by offical answer, is to do sorting:

public int majorityElement(int[] num) {
    if (num.length == 1) {
        return num[0];
    }

    Arrays.sort(num);
    return num[num.length / 2];
}

Third interesting solution is doing bit manipulation. Read Yanyulin’s blog for more.

Code

public class Solution {
    public int majorityElement(int[] num) {
        if (num == null || num.length == 0) {
            return 0;
        }
        int major = num[0];
        long count = 1;

        for (int i = 1; i < num.length; i++) {
            if (major == num[i]) {
                count++;
            } else if (count == 0) {
                major = num[i];
                count = 1;
            } else {
                count--;
            }
        }

        return major;
    }
}