问题描述

给定一个有序数组，其中所有元素都成对出现（出现两次），只有一个元素出现一次。要求在 O(log n) 的时间复杂度内找出这个唯一出现一次的元素。

例如：

  • [2, 2, 4, 4, 6, 6, 7, 8, 8, 9, 9] → 结果为 7
  • [1, 1, 2, 3, 3, 4, 4, 5, 5] → 结果为 2
  • [3, 3, 7, 7, 10, 11, 11] → 结果为 10

解题思路

这道题的关键在于利用有序数组的性质和二分查找来达到对数时间复杂度。核心观察是：

关键规律

在成对出现的数组中，如果所有元素都成对出现，那么每一对元素的第一个元素索引都是偶数（0-based）。当插入一个单独的元素后，该元素及其之后的所有成对元素的索引规律会被破坏。

具体来说：

  • 在单独元素出现之前，所有成对元素的第一个元素都位于偶数索引
  • 在单独元素出现之后，所有成对元素的第一个元素都位于奇数索引

算法设计

利用上述规律进行二分查找：

  1. 初始时，左指针指向数组开头，右指针指向数组末尾
  2. 计算中间位置 mid，并将其调整为偶数索引（如果 mid 是奇数，则减 1）
  3. 检查 digits[mid] 和 digits[mid + 1] 是否相等：
    • 如果相等，说明单独元素在 mid + 2 之后，将左指针移动到 mid + 2
    • 如果不相等，说明单独元素在 mid 或 mid 之前，将右指针移动到 mid
  4. 循环直到左右指针相遇，该位置即为单独元素

代码实现

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main()
{
    vector<int> digits = {2, 2, 4, 4, 6, 6, 7, 8, 8, 9, 9};

    int left = 0, right = digits.size() - 1;
    while (left < right)
    {
        int mid = left + (right - left) / 2;
        // 保证 mid 是偶数索引
        if (mid % 2 == 1)
        {
            mid--;
        }

        if (digits[mid] == digits[mid + 1])
        {
            // 单独元素在右侧
            left = mid + 2;
        }
        else
        {
            // 单独元素在左侧（包括 mid）
            right = mid;
        }
    }
    cout << digits[left];
}

运行结果

7

算法分析

  • 时间复杂度：O(log n)，标准的二分查找，每次循环将搜索范围缩小一半。
  • 空间复杂度：O(1)，只使用了常数个变量。

关键点总结

  1. 索引对齐：通过将 mid 调整为偶数索引，确保能正确比较成对元素
  2. 二分策略：根据 digits[mid] 和 digits[mid + 1] 是否相等来决定搜索方向
  3. 边界处理：
    • 当相等时，说明 mid 及其左侧都是正确的成对，单独元素在右侧
    • 当不相等时，说明单独元素在 mid 或左侧
  4. 循环条件：使用 left < right 而非 left <= right，确保循环终止时 left 和 right 指向同一位置

扩展思考

  • 如果数组不是完全成对（可能有多个单独出现的元素），该如何修改算法？
  • 如果数组中既有可能出现一次，也可能出现三次，该如何查找出现一次的元素？
  • 能否用异或运算解决？如果能，时间复杂度如何？复杂度为 O(n)，不满足题目 O(log n) 的要求