Majority Element

Method 1: HashMap is always a quick solution for this kind of problems.

public int majorityElement(int[] num) {

        Map<Integer,Integer> hm = new HashMap<Integer, Integer>();

        for (int i=0; i<num.length; i++) {

            if (!hm.containsKey(num[i])) {

                hm.put(num[i], 1);

            } else {

                hm.put(num[i],hm.get(num[i])+1);

                if (hm.get(num[i]) > num.length/2) {

                    return num[i];

                }

            }

        }

        return num[0];

    }

Method 2: Bit Manipulation

It is similar to Single Number.

public int majorityElement(int[] num) {

        

        //Bit manipulation

        int[] countsPerBit = new int[32];

        int result = 0;

        for (int i=0; i<32; i++) {

            int count = 0;

            for (int j=0; j<num.length; j++) {

                if((num[j]>>i&1) ==1) {

                    count++;

                }

            }

            if (count > num.length/2) {

                result |= (1<<i);

            }

        }

        return result;

    }

Method 3: Moore Voting Algorithm

This is super cool.

public int majorityElement(int[] num) {

        

        //Moore voting algorithm

        int elem = 0;

        int count = 0;

        

        for (int i=0; i<num.length; i++) {

            if (count == 0) {

                elem = num[i];

                count = 1;

            } else {

                if (elem == num[i]) {

                    count++;

                } else {

                    count--;

                }

            }

        }

        return elem;

    }