refactor 169

fishercoder1534 · fishercoder1534 · commit fb1e1e8f2dcb · 2021-10-12T08:11:59.000-07:00
diff --git a/src/main/java/com/fishercoder/solutions/_169.java b/src/main/java/com/fishercoder/solutions/_169.java
@@ -48,4 +48,26 @@ public int majorityElement(int[] nums) {
             return res;
         }
     }
+
+    public static class Solution3 {
+        /**
+         * I'm glad to have come up with this idea myself on 10/12/2021.
+         */
+        public int majorityElement(int[] nums) {
+            int count = 1;
+            int candidate = nums[0];
+            for (int i = 1; i < nums.length; i++) {
+                if (nums[i] != candidate) {
+                    count--;
+                    if (count < 0) {
+                        candidate = nums[i];
+                        count = 1;
+                    }
+                } else {
+                    count++;
+                }
+            }
+            return candidate;
+        }
+    }
 }
diff --git a/src/test/java/com/fishercoder/_169Test.java b/src/test/java/com/fishercoder/_169Test.java
@@ -0,0 +1,28 @@
+package com.fishercoder;
+
+import com.fishercoder.solutions._169;
+import org.junit.BeforeClass;
+import org.junit.Test;
+
+import static org.junit.Assert.assertEquals;
+
+public class _169Test {
+    private static _169.Solution1 solution1;
+    private static _169.Solution2 solution2;
+    private static _169.Solution3 solution3;
+
+    @BeforeClass
+    public static void setup() {
+        solution1 = new _169.Solution1();
+        solution2 = new _169.Solution2();
+        solution3 = new _169.Solution3();
+    }
+
+    @Test
+    public void test1() {
+        assertEquals(1, solution1.majorityElement(new int[]{1, 3, 1, 1, 4, 1, 1, 5, 1, 1, 6, 2, 2}));
+        assertEquals(1, solution2.majorityElement(new int[]{1, 3, 1, 1, 4, 1, 1, 5, 1, 1, 6, 2, 2}));
+        assertEquals(1, solution3.majorityElement(new int[]{1, 3, 1, 1, 4, 1, 1, 5, 1, 1, 6, 2, 2}));
+    }
+
+}
