目标
给你一个仅由整数组成的有序数组，其中每个元素都会出现两次，唯有一个数只会出现一次。
请你找出并返回只出现一次的那个数。
你设计的解决方案必须满足 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
思路
有序整数数组 nums，除了一个元素仅出现一次，其余每个元素都会出现两次，返回这个只出现一次的元素。
直接循环异或每个元素，时间复杂度为 O(n)。
题目要求时间复杂度是 O(logn) 显然需要使用二分查找，但是问题在于如果当前元素与其前/后元素相等，那么我们应该排除哪边？
这道题使用二分法的关键就是意识到 中间元素下标的奇偶性 与其前后元素的相等关系 可以判断只出现一次的元素在中间元素的哪边。
如果不考虑这个唯一元素，数组元素的排列一定是 a a b b c c ……，
- 如果
mid为偶数下标，nums[mid] == nums[mid + 1] - 如果
mid为奇数下标，nums[mid - 1] == nums[mid]
现在插入了一个唯一元素，那么该下标 后面 的关系变为：
- 如果
mid为偶数下标，nums[mid - 1] == nums[mid] - 如果
mid为奇数下标，nums[mid] == nums[mid + 1]
根据任意一组关系就可以判断唯一元素下标在 mid 的左侧还是右侧了。当 mid 为偶数，比较 nums[mid] == nums[mid + 1]，如果不相等说明在左侧，当 mid 为奇数，比较 nums[mid - 1] == nums[mid]，如果不等说明在左侧。即相等需要舍弃左边，不等舍弃右边。
官网题解给出了优化细节，省略奇偶性判断，直接比较 mid 与 mid^1 两个元素，当 mid 为奇数时，mid^1 = mid - 1，当 mid 为偶数时， mid^1 = mid + 1。
官网题解还给出了一种判断方法，由于唯一元素的下标一定是偶数，因此可以二分查找偶数下标，唯一元素以及它右侧的所有偶数下标都满足 nums[mid] != nums[mid + 1]，我们只需要找到第一个满足条件的下标即可。查找的过程需要保证 mid 为偶数，这样判断才能成立，通常的做法是得到 mid 之后判断其奇偶性，如果是奇数则减一。这里同样也有个优化细节，即 mid - (mid & 1) 可以保证 mid 为偶数。
代码
/**
* @date 2024-11-10 14:38
*/
public class SingleNonDuplicate540 {
public int singleNonDuplicate(int[] nums) {
int n = nums.length;
int l = 0;
int r = n - 1;
while (l < r) {
int mid = l + (r - l) / 2;
mid -= mid & 1;
if (nums[mid] != nums[mid + 1]) {
r = mid;
} else {
l = mid + 2;
}
}
return nums[l];
}
}
性能
