refactor 169

fishercoder1534 · fishercoder1534 · commit a423b86c822d · 2020-02-06T07:26:07.000-08:00
diff --git a/src/main/java/com/fishercoder/solutions/_169.java b/src/main/java/com/fishercoder/solutions/_169.java
@@ -1,29 +1,27 @@
 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*/
+    /**Moore Voting Algorithm
+     * How to understand this:
+     * 1. For a number to qualify as a majority element, it needs to occur more than 1/2 times, which
+     *          means there are a max of only one such element in any given array.
+     * 2. E.g. given this array [1,2,3,1,1,1], two of the 1s will be balanced off by 2 and 3, still there are two 1s remaining in the end
+     * which is the majority element*/
     public int majorityElement(int[] nums) {
       int count = 1;
       int majority = nums[0];
@@ -42,27 +40,6 @@ public int majorityElement(int[] nums) {
   }
 
   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
@@ -77,7 +54,7 @@ public int majorityElement(int[] nums) {
       //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
+                : 0;//we get rid of those that bits that are not part of the majority number
         res += bit[i] * (1 << (31 - i));
       }
       return res;
