LeetCode 540. 有序数组中的单一元素
题目描述
题意分析
数组已经有序，只有一个元素出现一次，其余元素都出现两次，所以相同元素一定相邻，数组长度也一定是奇数。要求在 $O(\log n)$ 时间、$O(1)$ 额外空间内返回这个单次元素。
线性扫描或异或都要访问整个数组。要使用二分，需要找到一种能判断答案在中点哪一侧的规律；这里的规律是相邻元素的配对位置。
解法：偶数下标二分
核心思路
[!blue]
设单次元素的下标为
p。它前面的元素全部两两配对，因此p必为偶数。在p之前，每一对占据「偶数下标、下一个奇数下标」；越过p后，后面的配对整体错开一位，改为从奇数下标开始。因此，对于一个偶数下标
mid，只需比较nums[mid]与nums[mid + 1]：
- 相等：这仍是一对正常配对的元素，说明
mid < p。这两个位置都不是答案，可以令left = mid + 2。- 不等：配对已在这里或更早的位置错开，说明
p <= mid。答案可能恰好在mid，所以令right = mid。始终把答案保留在闭区间
[left, right]内。初始的两端都是偶数；每轮把中点向下调整为偶数，更新后的两端也仍为偶数。只要left < right，区间至少有三个元素，调整后的mid <= right - 2，所以访问mid + 1不会越界。两个分支都会缩小区间，又不会丢掉答案。最终
left == right时，剩下的唯一位置就是p。
解题步骤
- 初始化
left = 0、right = n - 1，在left < right时循环。- 计算中点；若
mid为奇数，将其减一，确保它是一个候选数对的起点。- 若
nums[mid] == nums[mid + 1]，说明答案在这对元素之后，令left = mid + 2。- 否则令
right = mid，保留可能就是答案的mid。- 区间收敛后返回
nums[left]。
代码实现
class Solution {
public int singleNonDuplicate(int[] nums) {
int left = 0;
int right = nums.length - 1;
while (left < right) {
int mid = left + (right - left) / 2;
// 先把中点对齐到偶数下标，才能按配对是否错位判断方向。
if (mid % 2 == 1) {
mid--;
}
if (nums[mid] == nums[mid + 1]) {
// mid 与 mid+1 成对，单一元素在右侧。
left = mid + 2;
} else {
right = mid;
}
}
return nums[left];
}
}
func singleNonDuplicate(nums []int) int {
left := 0
right := len(nums) - 1
for left < right {
mid := left + (right-left)/2
// 先把中点对齐到偶数下标，才能按配对是否错位判断方向。
if mid%2 == 1 {
mid--
}
if nums[mid] == nums[mid+1] {
// 左侧配对完整，答案位于 [mid+2,right]，包含 mid+2。
left = mid + 2
} else {
right = mid
}
}
return nums[left]
}
复杂度分析
- 时间复杂度：$O(\log n)$，每轮排除约一半区间。
- 空间复杂度：$O(1)$，只使用常数个下标变量。
关键点总结
[!green]
- 有序性让相同元素相邻，单次元素让后续配对的起点由偶数变成奇数，形成可二分的分界。
- 偶数
mid与下一位相等，答案就在右侧；不等，答案就在mid或左侧。- 区间始终包含答案且两端都是偶数；单元素数组直接返回，答案位于首尾也无需特判。
易错点总结
[!yellow]
- 不把
mid对齐到偶数下标，会让「相等」的方向含义反转。- 将
mid向上调整可能使mid + 1越界；应在奇数时执行mid--。- 相等分支写成
left = mid + 1会保留这一对的后一项，破坏偶数边界及后续判断依据。- 不等时写
right = mid - 1可能跳过恰好位于mid的答案。- 循环条件必须是
left < right；单点区间继续访问mid + 1会越界。
转载与许可
许可
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！