540. 有序数组中的单一元素
题目描述
输入一个按非递减顺序排好的整数数组 nums。数组里只有一个值单独出现一次，其余每个值都恰好成对出现两次。
返回那个只出现一次的值。
算法的时间复杂度必须是 O(log n)，额外空间必须是 O(1)。
示例 1
输入：nums = [1,1,2,3,3,4,4,8,8] 输出：2
解释：除 2 以外，其余值都出现两次。
示例 2
输入：nums = [3,3,7,7,10,11,11] 输出：10
解释：10 只出现一次，其余值都成对。
数据范围
1 <= nums.length <= 10^50 <= nums[i] <= 10^5
解题思路：偶数下标二分查找
在单一元素左边，每一对数都从偶数下标开始：nums[偶] == nums[偶+1]；单一元素出现后，配对整体右移一位，这个等式不再成立。所以把 mid 调整成偶数，检查 nums[mid] 和 nums[mid+1]：相等说明单一元素在 mid+2 及右边，不等说明它在 mid 或左边。
为什么正确
单一元素始终在 [lo, hi] 内，且 lo 永远是偶数。
复杂度分析
时间 O(log n)，空间 O(1)。
易错点
忘记把 mid 对齐到偶数，或者相等时写成 lo = mid + 1，都会让 lo 变成奇数，破坏配对判断。
参考代码
Python、Java、C++、Go、JavaScript、TypeScript 六种语言，逻辑一致。
class Solution:
def singleNonDuplicate(self, nums: List[int]) -> int:
lo, hi = 0, len(nums) - 1
while lo < hi:
mid = (lo + hi) // 2
if mid % 2 == 1:
mid -= 1
if nums[mid] == nums[mid + 1]:
lo = mid + 2
else:
hi = mid
return nums[lo]class Solution {
public int singleNonDuplicate(int[] nums) {
int lo = 0, hi = nums.length - 1;
while (lo < hi) {
int mid = (lo + hi) / 2;
if (mid % 2 == 1) {
mid -= 1;
}
if (nums[mid] == nums[mid + 1]) {
lo = mid + 2;
} else {
hi = mid;
}
}
return nums[lo];
}
}class Solution {
public:
int singleNonDuplicate(vector<int>& nums) {
int lo = 0, hi = nums.size() - 1;
while (lo < hi) {
int mid = (lo + hi) / 2;
if (mid % 2 == 1) {
mid -= 1;
}
if (nums[mid] == nums[mid + 1]) {
lo = mid + 2;
} else {
hi = mid;
}
}
return nums[lo];
}
};func singleNonDuplicate(nums []int) int {
lo, hi := 0, len(nums)-1
for lo < hi {
mid := (lo + hi) / 2
if mid%2 == 1 {
mid -= 1
}
if nums[mid] == nums[mid+1] {
lo = mid + 2
} else {
hi = mid
}
}
return nums[lo]
}var singleNonDuplicate = function(nums) {
let lo = 0, hi = nums.length - 1;
while (lo < hi) {
let mid = Math.floor((lo + hi) / 2);
if (mid % 2 === 1) {
mid -= 1;
}
if (nums[mid] === nums[mid + 1]) {
lo = mid + 2;
} else {
hi = mid;
}
}
return nums[lo];
};function singleNonDuplicate(nums: number[]): number {
let lo = 0, hi = nums.length - 1;
while (lo < hi) {
let mid = Math.floor((lo + hi) / 2);
if (mid % 2 === 1) {
mid -= 1;
}
if (nums[mid] === nums[mid + 1]) {
lo = mid + 2;
} else {
hi = mid;
}
}
return nums[lo];
}其他解法
二分利用“单一元素之前的成对元素从偶数下标开始”这一有序结构，做到 O(log n)；异或不看顺序，只能 O(n)。
解法 2：全体异或 时间 O(n)，空间 O(1)
把所有元素依次异或。成对出现的数异或后抵消为 0。最后剩下的就是只出现一次的数。
不依赖数组有序，代码最短。但要遍历整个数组，达不到题目要求的 O(log n)；它是“只出现一次的数字”的通用解法，可以用来对照二分利用有序性带来的提速。
class Solution:
def singleNonDuplicate(self, nums: List[int]) -> int:
ans = 0
for x in nums:
ans ^= x
return ansclass Solution {
public int singleNonDuplicate(int[] nums) {
int ans = 0;
for (int x : nums) ans ^= x;
return ans;
}
}class Solution {
public:
int singleNonDuplicate(vector<int>& nums) {
int ans = 0;
for (int x : nums) ans ^= x;
return ans;
}
};func singleNonDuplicate(nums []int) int {
ans := 0
for _, x := range nums {
ans ^= x
}
return ans
}var singleNonDuplicate = function(nums) {
let ans = 0;
for (const x of nums) ans ^= x;
return ans;
};function singleNonDuplicate(nums: number[]): number {
let ans = 0;
for (const x of nums) ans ^= x;
return ans;
}