0540. Single Element in a Sorted Array¶
题目信息¶
- 题号:
0540
- 难度:
Medium
- 主题:
有序数组、唯一单次元素、成对元素、对数时间
- 原题:
- 重点:
恰有一个值出现一次、其他值都恰好出现两次、数组非递减、要求 O(log n) 时间和 O(1) 空间
题目重述¶
给定一个按非递减顺序排列的整数数组 nums。数组中恰好有一个元素只出现一次,其余每个元素都恰好出现两次。返回这个只出现一次的元素。
需要满足 O(log n) 时间复杂度和 O(1) 额外空间。重复元素的两份在排序后相邻,但唯一元素可能位于开头、中间或末尾。
自建示例¶
唯一元素位于中间:
输入:nums = [1,1,2,3,3,4,4]
输出:2
解释:1、3、4 都出现两次,只有 2 出现一次。
唯一元素位于末尾:
输入:nums = [0,0,5]
输出:5
解释:前两个元素构成一对,末尾的 5 没有配对。
唯一元素改变了成对下标的奇偶性¶
在唯一元素左侧,成对元素的第一份位于偶数下标、第二份位于奇数下标;越过唯一元素后,这种配对对齐会整体错一位。取中点并把它调整为偶数下标后,若 nums[mid] == nums[mid+1],唯一元素在右侧,否则在左侧(含中点)。
C++ 实现¶
class Solution {
public:
int singleNonDuplicate(std::vector<int>& nums) {
int left = 0;
int right = static_cast<int>(nums.size()) - 1;
while (left < right) {
int middle = left + (right - left) / 2;
if (middle % 2 == 1) --middle;
if (nums[middle] == nums[middle + 1]) {
left = middle + 2;
} else {
right = middle;
}
}
return nums[left];
}
};
代码分析¶
每次比较都根据配对是否完整排除一半区间,且把中点对齐到一对的起始下标,边界始终包含唯一元素。时间复杂度为 O(log n),额外空间复杂度为 O(1)。