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; } }