[数据结构与算法]Leetcode--Java--540. 有序数组中的单一元素

题目描述

给你一个仅由整数组成的有序数组，其中每个元素都会出现两次，唯有一个数只会出现一次。
请你找出并返回只出现一次的那个数。
你设计的解决方案必须满足 O(log n) 时间复杂度和 O(1) 空间复杂度。

样例描述

示例 1:

输入: nums = [1,1,2,3,3,4,4,8,8]
输出: 2
示例 2:

输入: nums =  [3,3,7,7,10,11,11]
输出: 10

思路

二分二段性思想 + 小技巧（脑筋急转弯）

1. 在插入元素之前，成对中第一个位置对应下标为偶数，第二个位置下标为奇数。在插入元素之后，反过来了。因此具备二段性
2. 因此可以依据二分位置下标的奇偶来判断
3. **小细节：**判断奇数与前一个位置比较，判断偶数与后一个位置比较，注意要防止越界。然后如果直接l = mid，在不相等的情况下，r = mid - 1直接否定了mid的位置，这里要调整为l = mid + 1 和r = mid。 因为虽然相等时答案是在右边，要封左边，但mid肯定不是答案。如果不相等，答案在左边，封右边时，mid可能正好就是那个插入值x

代码

class Solution {
    public int singleNonDuplicate(int[] nums) {
        int l = 0, r = nums.length - 1;
        while (l < r) {
            int mid = l + r >> 1;
            //偶数，与后面比较
            if (mid % 2 == 0) {
                if (mid + 1 <= r && nums[mid] == nums[mid + 1]) {
                    l = mid + 1;
                } else {
                    //保留mid，让l侧去否定mid
                    r = mid;
                } 
            } else {
                if (mid - 1 >= 0 && nums[mid] == nums[mid - 1]) {
                    l = mid + 1;
                } else {
                    r = mid;
                }
            }
        }
        return nums[l];
    }
}