0540. Single Element in a Sorted Array ====================================== 题目信息 -------- :题号: 0540 :难度: Medium :主题: 有序数组、唯一单次元素、成对元素、对数时间 :原题: `LeetCode 0540 `_ :重点: 恰有一个值出现一次、其他值都恰好出现两次、数组非递减、要求 O(log n) 时间和 O(1) 空间 题目重述 -------- 给定一个按非递减顺序排列的整数数组 ``nums``。数组中恰好有一个元素只出现一次,其余每个元素都恰好出现两次。返回这个只出现一次的元素。 需要满足 ``O(log n)`` 时间复杂度和 ``O(1)`` 额外空间。重复元素的两份在排序后相邻,但唯一元素可能位于开头、中间或末尾。 自建示例 -------- 唯一元素位于中间: .. code-block:: text 输入:nums = [1,1,2,3,3,4,4] 输出:2 解释:1、3、4 都出现两次,只有 2 出现一次。 唯一元素位于末尾: .. code-block:: text 输入:nums = [0,0,5] 输出:5 解释:前两个元素构成一对,末尾的 5 没有配对。 唯一元素改变了成对下标的奇偶性 ------------------------------ 在唯一元素左侧,成对元素的第一份位于偶数下标、第二份位于奇数下标;越过唯一元素后,这种配对对齐会整体错一位。取中点并把它调整为偶数下标后,若 ``nums[mid] == nums[mid+1]``,唯一元素在右侧,否则在左侧(含中点)。 C++ 实现 -------- .. code-block:: cpp class Solution { public: int singleNonDuplicate(std::vector& nums) { int left = 0; int right = static_cast(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)``。