题目描述

给定一个只包含整数的有序数组，每个元素都会出现两次，唯有一个数只会出现一次，找出这个数。

样例

输入: [1,1,2,3,3,4,4,8,8]
输出: 2

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

注意

• 您的解法仅能使用 $O(\log n)$ 时间复杂度和 $O(1)$ 空间复杂度。

算法

(倍增) $O(\log n)$

1. 倍增的核心思想是每次尝试向前移动 2 的幂次，如果发现此时已经不合法，故减少幂次，重新尝试移动。若合法，则尝试成功，向前移动 2 的幂次。
2. 倍增应该从最大可能移动的 2 的幂次开始尝试，每次尝试后，无论是否合法，都需要降低一个幂次。
3. 对于此题，最多可以移动的步数为 $floor(\log n)$，最少可以移动的步数为 2 步。
4. 故先找到最大的 2 的幂次，开始尝试移动，判断合法的条件为，若 nums[start + step] == nums[start + step + 1] 成立，则合法，start += step；然后尝试之后 step /= 2 直到 step = 1 为止。
5. 最后答案为 nums[start + 2]，这里的加 2 请读者自己思考。
6. 以上做法需要特判 nums[0] 就是出现一次的元素。

时间复杂度

• 倍增每次降低 2 的一个幂次，最多降低 $floor(\log n)$ 次，故时间复杂度为 $O(\log n)$。

C++ 代码

class Solution {
public:
    int singleNonDuplicate(vector<int>& nums) {
        int n = nums.size();
        if (n == 1 || nums[0] != nums[1])
            return nums[0];
        int start = 0, step = 1;

        while (step * 2 < n)
            step *= 2;

        while (step >= 2) {
            if (start + step < n - 1 && nums[start + step] == nums[start + step + 1])
                start += step;
            step /= 2;
        }

        return nums[start + 2];
    }
};