LeetCode LCR 070. 有序数组中的单一元素
题目描述
题意分析
升序数组中，只有一个元素出现一次，其余元素都恰好出现两次，要求返回这个单独元素的值。进阶要求时间为 $O(\log n)$、额外空间为 $O(1)$，需要利用有序性定位它。
排序使相同元素相邻。单独元素之前的元素能够完整分成若干对，所以单独元素的下标必为偶数，整个数组长度必为奇数；答案可能在任意一端，也可能就是长度为一的数组中的唯一元素。
解法：按奇偶配对关系二分
核心思路
[!blue]
从下标零开始，原本应当把相邻的偶数下标与奇数下标配成一组。单独元素出现之前，真实相等对正好符合这个分组；单独元素占去一个位置之后，后续相等对便整体错位，变成“奇数下标在前、偶数下标在后”。
因此只需检查某个位置是否仍与原分组中的伙伴相等。用
mid ^ 1得到这个伙伴：偶数下标加一，奇数下标减一。若两值相等，mid仍在单独元素左侧，答案必在更右边；若不等，说明已经到达或越过错位点，答案在mid或其左侧。维护闭区间
[left,right]始终包含答案。匹配时令left = mid+1，排除已确认完整配对的左侧；不匹配时令right = mid，保留可能就是答案的中点。区间不断缩小，最终只剩一个位置。配对访问安全的原因是循环条件
left < right：向下取整的中点始终满足mid < right <= n-1。偶数中点的伙伴mid+1不超过最后下标；奇数中点至少为一，伙伴mid-1也不会为负。并不是靠强行调整中点奇偶来避免越界。
解题步骤
- 初始化
left = 0、right = n-1，将两端可能的答案都纳入候选。- 当
left < right时，取下中点，比较nums[mid]与nums[mid ^ 1]。- 相等就排除中点及其左侧；不相等就把中点保留为右边界。
- 两端相等后返回
nums[left]，题目要的是元素值。长度为一时不执行配对访问，直接返回唯一元素。若答案在最后一位，二分会逐步将左边界推到最后，但不会拿最后的偶数下标去访问它右边不存在的伙伴。
代码实现
class Solution {
public int singleNonDuplicate(int[] nums) {
int left = 0;
int right = nums.length - 1;
while (left < right) {
int mid = (left + right) >> 1;
if (nums[mid] != nums[mid ^ 1]) {
right = mid;
} else {
left = mid + 1;
}
}
return nums[left];
}
}
func singleNonDuplicate(nums []int) int {
left, right := 0, len(nums)-1
for left < right {
mid := (left + right) >> 1
if nums[mid] != nums[mid^1] {
right = mid
} else {
left = mid + 1
}
}
return nums[left]
}
复杂度分析
- 时间复杂度：$O(\log n)$，每轮只做一次配对比较，并将候选数量缩小约一半。
- 空间复杂度：$O(1)$，只维护二分下标。
关键点总结
[!green]
- 二分依据是配对关系在唯一元素处发生错位，而不是元素与某个已知目标的大小关系。
mid ^ 1只是按原来的偶奇分组寻找伙伴，真正的边界安全来自下中点严格小于右端点。- 不匹配时中点仍可能是答案，需要保留；匹配时中点已经确定在答案左侧，可以排除。
易错点总结
[!yellow]
- 把循环写成
left <= right后仍直接访问配对伙伴，会在只剩最后一个位置时越界。- 匹配时令
left = mid，两候选区间可能无法继续缩小。- 不匹配时令
right = mid-1，可能丢掉单独元素本身。- 返回下标或随意调整中点奇偶，却没有同步修改区间更新逻辑。
转载与许可
许可
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！