LeetCode 540.有序数组中的单一元素

题目描述

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

示例 1:

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

示例 2:

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

注意: 您的方案应该在 O(log n)时间复杂度和 O(1)空间复杂度中运行。

解法分析

题目中要求 log n 的时间复杂度，已经提示不能直接遍历，我们可以考虑二分查找。

我们看下图，如果所有数字成对出现，则偶数位置的数字应该与它右边的数字相等；相应地，奇数位置的数字应该与它左边的数字相等。否则，说明当前位置左侧已经出现了唯一的数字。

我们把这个作为二分查找缩小范围的条件：

• 当前为偶位置，但与右边数字不相等 -->向左查找；
• 当前为奇位置，但与左边数字不相等 -->向左查找。

代码示例（C++）

class Solution {
public:
    int singleNonDuplicate(vector<int>& nums) {
        int left = 0;
        int right = nums.size() - 1;
        int mid = 0;

        if (nums.size() == 1 || nums[0] != nums[1]) // 数组长度为1，或第一个数字就是唯一数字
            return nums[0];

        while (mid = (left + right) / 2, left < right) {

            if (mid % 2 == 0) { // 下标为偶数。如果左侧都是成对出现的数字，其值应与右边相等
                if (nums[mid] != nums[mid + 1] && nums[mid] != nums[mid - 1])
                    return nums[mid];

                if (nums[mid] != nums[mid + 1])
                    right = mid - 1;
                else
                    left = mid + 1;
            }
            else { // 下标为奇数。如果左侧都是成对出现的数字，其值应与左边相等
                if (nums[mid] != nums[mid + 1] && nums[mid] != nums[mid - 1])
                    return nums[mid];

                if (nums[mid] != nums[mid - 1])
                    right = mid - 1;
                else
                    left = mid + 1;
            }
        }

        return nums[mid];
    }
};