169. Majority Element

Easy

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.

Example 1:

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

Example 2:

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

package leetcode.easy;

import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;
import java.util.Random;

public class MajorityElement {
@org.junit.Test
public void test() {
int[] nums1 = { 3, 2, 3 };
int[] nums2 = { 2, 2, 1, 1, 1, 2, 2 };
System.out.println(majorityElement1(nums1));
System.out.println(majorityElement1(nums2));
System.out.println(majorityElement2(nums1));
System.out.println(majorityElement2(nums2));
System.out.println(majorityElement3(nums1));
System.out.println(majorityElement3(nums2));
System.out.println(majorityElement4(nums1));
System.out.println(majorityElement4(nums2));
System.out.println(majorityElement5(nums1));
System.out.println(majorityElement5(nums2));
System.out.println(majorityElement6(nums1));
System.out.println(majorityElement6(nums2));
}

public int majorityElement1(int\[\] nums) {  
    int majorityCount = nums.length / 2;

    for (int num : nums) {  
        int count = 0;  
        for (int elem : nums) {  
            if (elem == num) {  
                count += 1;  
            }  
        }

        if (count > majorityCount) {  
            return num;  
        }  
    }

    return -1;  
}

private Map<Integer, Integer> countNums(int\[\] nums) {  
    Map<Integer, Integer> counts = new HashMap<Integer, Integer>();  
    for (int num : nums) {  
        if (!counts.containsKey(num)) {  
            counts.put(num, 1);  
        } else {  
            counts.put(num, counts.get(num) + 1);  
        }  
    }  
    return counts;  
}

public int majorityElement2(int\[\] nums) {  
    Map<Integer, Integer> counts = countNums(nums);

    Map.Entry<Integer, Integer> majorityEntry = null;  
    for (Map.Entry<Integer, Integer> entry : counts.entrySet()) {  
        if (majorityEntry == null || entry.getValue() > majorityEntry.getValue()) {  
            majorityEntry = entry;  
        }  
    }

    return majorityEntry.getKey();  
}

public int majorityElement3(int\[\] nums) {  
    Arrays.sort(nums);  
    return nums\[nums.length / 2\];  
}

private int randRange(Random rand, int min, int max) {  
    return rand.nextInt(max - min) + min;  
}

private int countOccurences(int\[\] nums, int num) {  
    int count = 0;  
    for (int i = 0; i < nums.length; i++) {  
        if (nums\[i\] == num) {  
            count++;  
        }  
    }  
    return count;  
}

public int majorityElement4(int\[\] nums) {  
    Random rand = new Random();

    int majorityCount = nums.length / 2;

    while (true) {  
        int candidate = nums\[randRange(rand, 0, nums.length)\];  
        if (countOccurences(nums, candidate) > majorityCount) {  
            return candidate;  
        }  
    }  
}

private int countInRange(int\[\] nums, int num, int lo, int hi) {  
    int count = 0;  
    for (int i = lo; i <= hi; i++) {  
        if (nums\[i\] == num) {  
            count++;  
        }  
    }  
    return count;  
}

private int majorityElementRec(int\[\] nums, int lo, int hi) {  
    // base case; the only element in an array of size 1 is the majority  
    // element.  
    if (lo == hi) {  
        return nums\[lo\];  
    }

    // recurse on left and right halves of this slice.  
    int mid = (hi - lo) / 2 + lo;  
    int left = majorityElementRec(nums, lo, mid);  
    int right = majorityElementRec(nums, mid + 1, hi);

    // if the two halves agree on the majority element, return it.  
    if (left == right) {  
        return left;  
    }

    // otherwise, count each element and return the "winner".  
    int leftCount = countInRange(nums, left, lo, hi);  
    int rightCount = countInRange(nums, right, lo, hi);

    return leftCount > rightCount ? left : right;  
}

public int majorityElement5(int\[\] nums) {  
    return majorityElementRec(nums, 0, nums.length - 1);  
}

public int majorityElement6(int\[\] nums) {  
    int count = 0;  
    Integer candidate = null;

    for (int num : nums) {  
        if (count == 0) {  
            candidate = num;  
        }  
        count += (num == candidate) ? 1 : -1;  
    }

    return candidate;  
}  

}