540. Single Element in a Sorted Array - Medium

前往題目

想法

• Binary Search

思路

規律是只要pair第一個數字不在偶數位上，就代表當前位置已在單一個數字之後，所以規律被打亂了

例如:[1, 1, 3, 3, 2, 4, 4]，1和3組合是第一個在偶數位，第二個在奇數位，當單一數字2出現後，組合4的位置就被打亂了，變成第一個數字在奇數位，而第二個數字在偶數位。因為只有一個單一數字，所以規則一定會被打亂

1. binary search，每次判斷mid位置的數字規律是否是正常的
2. 正常的話就往右邊找
3. 不正常的話就往左邊找

不想判斷邊界條件的話循環條件直接l < r就好，反正收斂到最後一個數字不用判斷，一定是答案

Code

網友解答

class Solution {
    public int singleNonDuplicate(int[] nums) {
        if (nums.length == 1) return nums[0];

        int l = 0, r = nums.length - 1;

        while (l < r) {
            int mid = l + (r - l) / 2;

            // In the pattern
            if ((mid % 2 == 0 && nums[mid] == nums[mid + 1]) ||
                (mid % 2 == 1 && nums[mid - 1] == nums[mid])) {
                l = mid + 1;
            } else {
                r = mid;
            }
        }

        return nums[l];
    }
}