refactor 229

fishercoder1534 · fishercoder1534 · commit 1314e8d41736 · 2020-02-06T07:27:41.000-08:00
diff --git a/src/main/java/com/fishercoder/solutions/_229.java b/src/main/java/com/fishercoder/solutions/_229.java
@@ -1,15 +1,21 @@
 package com.fishercoder.solutions;
 
 import java.util.ArrayList;
-import java.util.HashMap;
 import java.util.List;
-import java.util.Map;
 
 /**
  * 229. Majority Element II
  *
  * Given an integer array of size n, find all elements that appear more than ⌊ n/3 ⌋ times.
  * The algorithm should run in linear time and in O(1) space.
+ *
+ * Example 1:
+ * Input: [3,2,3]
+ * Output: [3]
+ *
+ * Example 2:
+ * Input: [1,1,1,3,3,2,2,2]
+ * Output: [1,2]
 
  Hint:
  How many majority elements could it possibly have?
@@ -18,29 +24,9 @@
 public class _229 {
 
     public static class Solution1 {
-        public List<Integer> majorityElement(int[] nums) {
-            Map<Integer, Integer> counterMap = new HashMap();
-            for (int i = 0; i < nums.length; i++) {
-                if (counterMap.containsKey(nums[i])) {
-                    counterMap.put(nums[i], counterMap.get(nums[i]) + 1);
-                } else {
-                    counterMap.put(nums[i], 1);
-                }
-            }
-            int size = nums.length;
-            List<Integer> result = new ArrayList<>();
-            for (Integer i : counterMap.keySet()) {
-                int threshold = size / 3;
-                if (counterMap.get(i) > threshold) {
-                    result.add(i);
-                }
-            }
-            return result;
-        }
-    }
-
-    public static class Solution2 {
-        /**Moore Voting algorithm*/
+        /**Moore Voting algorithm:
+         * This is an extension of Majority Element I, instead of one one majority, there could be a max of two majority elements,
+         * so we'll just use two counters to do the job.*/
         public List<Integer> majorityElement(int[] nums) {
             List<Integer> result = new ArrayList<>();
             if (nums == null || nums.length == 0) {
@@ -70,20 +56,15 @@ public List<Integer> majorityElement(int[] nums) {
             count2 = 0;
             for (int num : nums) {
                 if (num == candidate1) {
-                    count1 += 2;
-                } else {
-                    count1--;
-                }
-                if (num == candidate2) {
-                    count2 += 2;
-                } else {
-                    count2--;
+                    count1++;
+                } else if (num == candidate2) {
+                    count2++;
                 }
             }
-            if (count1 > 0) {
+            if (count1 > nums.length/3) {
                 result.add(candidate1);
             }
-            if (count2 > 0) {
+            if (count2 > nums.length/3) {
                 result.add(candidate2);
             }
             return result;
diff --git a/src/test/java/com/fishercoder/_229Test.java b/src/test/java/com/fishercoder/_229Test.java
@@ -9,54 +9,60 @@
 import static org.junit.Assert.assertEquals;
 
 public class _229Test {
-    private static _229.Solution2 solution2;
+    private static _229.Solution1 solution1;
     private static int[] nums;
 
     @BeforeClass
     public static void setup() {
-        solution2 = new _229.Solution2();
+        solution1 = new _229.Solution1();
     }
 
     @Test
     public void test1() {
         nums = new int[]{1};
-        assertEquals(Arrays.asList(1), solution2.majorityElement(nums));
+        assertEquals(Arrays.asList(1), solution1.majorityElement(nums));
     }
 
     @Test
     public void test2() {
         nums = new int[]{1, 2};
-        assertEquals(Arrays.asList(2, 1), solution2.majorityElement(nums));
+        assertEquals(Arrays.asList(2, 1), solution1.majorityElement(nums));
     }
 
     @Test
     public void test3() {
         nums = new int[]{2, 2};
-        assertEquals(Arrays.asList(2), solution2.majorityElement(nums));
+        assertEquals(Arrays.asList(2), solution1.majorityElement(nums));
     }
 
     @Test
     public void test4() {
         nums = new int[]{1, 2, 3};
-        assertEquals(Arrays.asList(), solution2.majorityElement(nums));
+        assertEquals(Arrays.asList(), solution1.majorityElement(nums));
     }
 
     @Test
     public void test5() {
         nums = new int[]{3, 2, 3};
-        assertEquals(Arrays.asList(3), solution2.majorityElement(nums));
+        assertEquals(Arrays.asList(3), solution1.majorityElement(nums));
     }
 
     @Test
     public void test6() {
         nums = new int[]{3, 3, 4};
-        assertEquals(Arrays.asList(3), solution2.majorityElement(nums));
+        assertEquals(Arrays.asList(3), solution1.majorityElement(nums));
     }
 
     @Test
     public void test7() {
         nums = new int[]{2, 2, 1, 3};
-        assertEquals(Arrays.asList(2), solution2.majorityElement(nums));
+        assertEquals(Arrays.asList(2), solution1.majorityElement(nums));
+    }
+
+    @Test
+    public void test8() {
+        nums = new int[]{2, 2, 3, 3, 2, 4};
+        assertEquals(Arrays.asList(2), solution1.majorityElement(nums));
     }
 
 }
