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 <= nums.length <= 10^5
0 <= nums[i] <= 10^5

思路

一看是有序的，题目又要求时间常数空间，那么大概率就是二分了。

那我们对于一个位置如何判断是否向左向右呢？

首先，如果当前元素的左右两边都和自身不同，那么就是答案。

不是第一种情况的话，就是左边或者右边有一个和当前元素一样，如果是左边一样的话，即如果，此时，如果单一元素在左边，一定为偶数，如果单一元素在右边，mid一定为奇数，这是很好理解的，因为唯一的元素只有一个，剩下的都是成对。这样就可以判断是往左还是往右查找。最终可以得到结论，如果满足下面两种情况之一就往右边找，反之往左边找。

• 是奇数且
• 是偶数且

Ps1.通过可以看出代码中并没有比较大小，只是在比较是否相等，所以输入是不是有序的并不重要，不有序也可以找出唯一的那个元素。

Ps2.看了别人的解法和官解，好多都用了位运算，很强，下面代码中第一个”else if”的条件可以合并为nums[mid] == nums[mid ^ 1]，因为当mid是偶数时，mid + 1 == mid ^ 1；当mid是奇数时，mid - 1 == mid ^ 1。

代码

class Solution {
    public int singleNonDuplicate(int[] nums) {
        int n = nums.length;
        int left = 0;
        int right = n - 1;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if ((mid == 0 || nums[mid - 1] != nums[mid]) && (mid == n - 1 || nums[mid + 1] != nums[mid])) {
                return nums[mid];
            } else if (mid % 2 == 1 && nums[mid - 1] == nums[mid] || mid % 2 == 0 && nums[mid + 1] == nums[mid]) { // 这个else if 的判断等同于 nums[mid] == nums[mid ^ 1]
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        return -1;
    }
}