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

@@ -33,82 +33,8 @@
 s;%0A%0A
-import java.util.Arrays;%0Aimport java.util.HashMap;%0Aimport java.util.Map;%0A%0A
 /**%0A
@@ -187,17 +187,16 @@
  times.%0A
-%0A
  You may
@@ -296,17 +296,16 @@
 mple 1:%0A
-%0A
  Input: 
@@ -336,17 +336,16 @@
 mple 2:%0A
-%0A
  Input: 
@@ -458,16 +458,407 @@
 lgorithm
+%0A     * How to understand this:%0A     * 1. For a number to qualify as a majority element, it needs to occur more than 1/2 times, which%0A     *          means there are a max of only one such element in any given array.%0A     * 2. E.g. given this array %5B1,2,3,1,1,1%5D, two of the 1s will be balanced off by 2 and 3, still there are two 1s remaining in the end%0A     * which is the majority element
 */%0A    p
@@ -1256,501 +1256,8 @@
 2 %7B%0A
-    public int majorityElement(int%5B%5D nums) %7B%0A      Map%3CInteger, Integer%3E map = new HashMap();%0A      for (int i : nums) %7B%0A        map.put(i, map.getOrDefault(i, 0) + 1);%0A        if (map.get(i) %3E nums.length / 2) %7B%0A          return i;%0A        %7D%0A      %7D%0A      return -1;%0A    %7D%0A  %7D%0A%0A  public static class Solution3 %7B%0A    //This is O(nlogn) time.%0A    public int majorityElement(int%5B%5D nums) %7B%0A      Arrays.sort(nums);%0A      return nums%5Bnums.length / 2%5D;%0A    %7D%0A  %7D%0A%0A  public static class Solution4 %7B%0A
     
@@ -1866,16 +1866,20 @@
 / 2 ? 1%0A
+    
         

refactor 169