add a solution for 540

fishercoder1534 · fishercoder1534 · commit 132ec4742292 · 2021-11-19T17:10:07.000-08:00
diff --git a/README.md b/README.md
@@ -762,7 +762,7 @@ _If you like this project, please leave me a star._ &#9733;
 |543|[Diameter of Binary Tree](https://leetcode.com/problems/diameter-of-binary-tree/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_543.java) | | Easy | Tree/DFS/Recursion
 |542|[01 Matrix](https://leetcode.com/problems/01-matrix/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_542.java) |  |Medium | BFS
 |541|[Reverse String II](https://leetcode.com/problems/reverse-string-ii/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_541.java) |  |Easy | String
-|540|[Single Element in a Sorted Array](https://leetcode.com/problems/single-element-in-a-sorted-array/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_540.java) |  |Medium | 
+|540|[Single Element in a Sorted Array](https://leetcode.com/problems/single-element-in-a-sorted-array/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_540.java) |  |Medium |Array, Binary Search 
 |539|[Minimum Time Difference](https://leetcode.com/problems/minimum-time-difference/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_539.java) | | Medium | String
 |538|[Convert BST to Greater Tree](https://leetcode.com/problems/convert-bst-to-greater-tree/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_538.java) |  |Easy | Tree
 |537|[Complex Number Multiplication](https://leetcode.com/problems/complex-number-multiplication/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_537.java) |  |Medium | Math, String
diff --git a/src/main/java/com/fishercoder/solutions/_540.java b/src/main/java/com/fishercoder/solutions/_540.java
@@ -30,4 +30,33 @@ public int singleNonDuplicate(int[] nums) {
             return nums[start];
         }
     }
+
+    public static class Solution3 {
+        public int singleNonDuplicate(int[] nums) {
+            int left = 0;
+            int right = nums.length - 1;
+            while (left < right) {
+                int mid = left + (right - left) / 2;
+                if (nums[mid] != nums[mid + 1] && nums[mid] != nums[mid - 1]) {
+                    return nums[mid];
+                }
+                if (nums[mid] != nums[mid + 1]) {
+                    if ((right - mid) % 2 == 0) {
+                        if (right != mid) {
+                            right = mid;
+                        } else {
+                            return nums[mid];
+                        }
+                    } else {
+                        left = mid + 1;
+                    }
+                } else if ((right - mid) % 2 == 0 && right != mid) {
+                    left = mid + 1;
+                } else {
+                    right = mid - 1;
+                }
+            }
+            return nums[left];
+        }
+    }
 }
diff --git a/src/test/java/com/fishercoder/_540Test.java b/src/test/java/com/fishercoder/_540Test.java
@@ -9,32 +9,50 @@
 public class _540Test {
     private static _540.Solution1 solution1;
     private static _540.Solution2 solution2;
+    private static _540.Solution3 solution3;
     private static int[] nums;
+    private static int expected;
 
     @BeforeClass
     public static void setup() {
         solution1 = new _540.Solution1();
         solution2 = new _540.Solution2();
+        solution3 = new _540.Solution3();
     }
 
     @Test
     public void test1() {
         nums = new int[]{1, 1, 2, 3, 3, 4, 4, 8, 8};
-        assertEquals(2, solution1.singleNonDuplicate(nums));
-        assertEquals(2, solution2.singleNonDuplicate(nums));
+        expected = 2;
+        assertEquals(expected, solution1.singleNonDuplicate(nums));
+        assertEquals(expected, solution2.singleNonDuplicate(nums));
+        assertEquals(expected, solution3.singleNonDuplicate(nums));
     }
 
     @Test
     public void test2() {
         nums = new int[]{3, 3, 7, 7, 10, 11, 11};
-        assertEquals(10, solution1.singleNonDuplicate(nums));
-        assertEquals(10, solution2.singleNonDuplicate(nums));
+        expected = 10;
+        assertEquals(expected, solution1.singleNonDuplicate(nums));
+        assertEquals(expected, solution2.singleNonDuplicate(nums));
+        assertEquals(expected, solution3.singleNonDuplicate(nums));
     }
 
     @Test
     public void test3() {
         nums = new int[]{1, 1, 2};
-        assertEquals(2, solution1.singleNonDuplicate(nums));
-        assertEquals(2, solution2.singleNonDuplicate(nums));
+        expected = 2;
+        assertEquals(expected, solution1.singleNonDuplicate(nums));
+        assertEquals(expected, solution2.singleNonDuplicate(nums));
+        assertEquals(expected, solution3.singleNonDuplicate(nums));
+    }
+
+    @Test
+    public void test4() {
+        nums = new int[]{1, 1, 2, 2, 3};
+        expected = 3;
+        assertEquals(expected, solution1.singleNonDuplicate(nums));
+        assertEquals(expected, solution2.singleNonDuplicate(nums));
+        assertEquals(expected, solution3.singleNonDuplicate(nums));
     }
 }
