problem 540#

给你一个仅由整数组成的有序数组，其中每个元素都会出现两次，唯有一个数只会出现一次。

请你找出并返回只出现一次的那个数。

你设计的解决方案必须满足 O(log n) 时间复杂度和 O(1) 空间复杂度。

示例 1:

输入: nums = [1,1,2,3,3,4,4,8,8] 输出: 2 示例 2:

输入: nums = [3,3,7,7,10,11,11] 输出: 10

提示:

1 <= nums.length <= 105 0 <= nums[i] <= 105

qwen answer#

你好，奋进者！

这道题要求时间复杂度为 $O(\log n)$，这提示我们需要使用 二分查找（Binary Search）。虽然数组有序，但不能直接根据数值大小二分，而是要根据 下标的奇偶性与数值配对关系 来进行二分。

解题思路#

1. 观察规律：

   • 在单一元素出现之前，成对的元素占据的下标是 (偶数, 奇数)，例如 (0, 1), (2, 3)。此时 nums[i] == nums[i+1]（其中 i 为偶数）。
   • 在单一元素出现之后，由于中间插入了一个单独的元素，成对元素的下标变成了 (奇数, 偶数)，例如 (3, 4), (5, 6)。此时 nums[i] == nums[i-1]（其中 i 为奇数）。

2. 二分策略：

   • 我们取中间位置 mid。
   • 利用异或运算 mid ^ 1 可以快速找到 mid 的配对位置：
     • 如果 mid 是偶数，mid ^ 1 等于 mid + 1。
     • 如果 mid 是奇数，mid ^ 1 等于 mid - 1。
   • 如果 nums[mid] == nums[mid ^ 1]，说明当前处于单一元素的 左侧（配对规律未被打乱），单一元素在右半部分，调整 left = mid + 1。
   • 如果 nums[mid] != nums[mid ^ 1]，说明当前处于单一元素的 右侧 或者 mid 就是单一元素，调整 right = mid。

3. 复杂度：

   • 时间复杂度：$O(\log n)$，每次迭代将搜索范围减半。
   • 空间复杂度：$O(1)$，只使用了常数个变量。

C++ 代码实现#

#include <vector>

using namespace std;

class Solution {
public:
    int singleNonDuplicate(vector<int>& nums) {
        int left = 0;
        int right = nums.size() - 1;
        
        while (left < right) {
            int mid = left + (right - left) / 2;
            
            // 利用异或运算找到配对的索引
            // 如果 mid 是偶数，mid ^ 1 是 mid + 1
            // 如果 mid 是奇数，mid ^ 1 是 mid - 1
            if (nums[mid] == nums[mid ^ 1]) {
                // 配对正常，说明单一元素在右侧
                left = mid + 1;
            } else {
                // 配对异常，说明单一元素在左侧或就是 mid
                right = mid;
            }
        }
        
        // 循环结束时 left == right，即为单一元素的下标
        return nums[left];
    }
};

代码简析#

• mid ^ 1 技巧：这是本题的核心技巧，避免了繁琐的奇偶判断 if-else，直接定位到当前 mid 应该配对的另一个元素位置。
• 循环条件：left < right 保证搜索空间缩小到 1 时停止，此时 left 指向的就是目标元素。
• 边界处理：由于题目保证一定有一个单一元素且数组长度为奇数，不需要额外的边界检查。