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 <= 10^5
• 0 <= nums[i] <= 10^5

解答

思路

nums 的长度一定是奇数，因此中点处有两种情况：

• [11, 11, 12, 12, 13] 此时 nums[2] == nums[3]，说明所求元素在右半部分
• [10, 11, 11, 12, 12] 此时 nums[2] != nums[3]，说明所求元素在左半部分
• 也就是说所求元素一定是第一个 False 的元素
  • [True, True, True, True, False]
  • [False, False, False, False, False]
  • 所谓的 二段性

代码

C++ 代码

class Solution {
public:
    int singleNonDuplicate(vector<int>& nums) {
        int n = nums.size();

        int l = 0;
        int r = n - 1;

        while (l <= r) {
            int mid = l + r >> 1;

            if (mid % 2 == 0) {
                if (mid + 1 < n && nums[mid] == nums[mid + 1]) {
                    l = mid + 1;
                }
                else {
                    r = mid - 1;
                }
            }
            else {
                if (mid - 1 >= 0 && nums[mid] == nums[mid - 1]) {
                    l = mid + 1;
                }
                else {
                    r = mid - 1;
                }
            }
        }

        return nums[l];
    }
};