_169.java

package com.fishercoder.solutions;

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

/**
 * 169. Majority Element

 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
 */
public class _169 {
  public static class Solution1 {
    /**Moore Voting Algorithm*/
    public int majorityElement(int[] nums) {
      int count = 1;
      int majority = nums[0];
      for (int i = 1; i < nums.length; i++) {
        if (count == 0) {
          count++;
          majority = nums[i];
        } else if (nums[i] == majority) {
          count++;
        } else {
          count--;
        }
      }
      return majority;
    }
  }

  public static class Solution2 {
    public int majorityElement(int[] nums) {
      Map<Integer, Integer> map = new HashMap();
      for (int i : nums) {
        map.put(i, map.getOrDefault(i, 0) + 1);
        if (map.get(i) > nums.length / 2) {
          return i;
        }
      }
      return -1;
    }
  }

  public static class Solution3 {
    //This is O(nlogn) time.
    public int majorityElement(int[] nums) {
      Arrays.sort(nums);
      return nums[nums.length / 2];
    }
  }

  public static class Solution4 {
    //bit manipulation
    public int majorityElement(int[] nums) {
      int[] bit = new int[32];//because an integer is 32 bits, so we use an array of 32 long
      for (int num : nums) {
        for (int i = 0; i < 32; i++) {
          if ((num >> (31 - i) & 1) == 1) {
            bit[i]++;//this is to compute each number's ones frequency
          }
        }
      }
      int res = 0;
      //this below for loop is to construct the majority element: since every bit of this element would have appeared more than n/2 times
      for (int i = 0; i < 32; i++) {
        bit[i] = bit[i] > nums.length / 2 ? 1
            : 0;//we get rid of those that bits that are not part of the majority number
        res += bit[i] * (1 << (31 - i));
      }
      return res;
    }
  }
}