refactor 169

fishercoder1534 · fishercoder1534 · commit e1bdc1da8f4f · 2021-07-16T11:56:06.000-07:00
diff --git a/src/main/java/com/fishercoder/solutions/_169.java b/src/main/java/com/fishercoder/solutions/_169.java
@@ -1,63 +1,51 @@
 package com.fishercoder.solutions;
 
-/**
- * 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
-     * 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];
-      for (int i = 1; i < nums.length; i++) {
-        if (count == 0) {
-          count++;
-          majority = nums[i];
-        } else if (nums[i] == majority) {
-          count++;
-        } else {
-          count--;
+    public static class Solution1 {
+        /**
+         * 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];
+            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;
         }
-      }
-      return majority;
     }
-  }
 
-  public static class Solution2 {
-    //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
-          }
+    public static class Solution2 {
+        //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;
         }
-      }
-      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;
     }
-  }
 }
