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

1.题目基本信息

1.1.题目描述

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

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

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

1.2.题目地址

https://leetcode.cn/problems/single-element-in-a-sorted-array/description/

2.解题方法

2.1.解题思路

二分查找（红蓝染色法）

2.2.解题步骤

第一步，确定红蓝染色的特征。特征一：红：位置i处值与处于同一对的元素相等；蓝：位置i处值与处于同一对的元素不相等（如果i为奇数，相邻元素取右边的偶数，反之取左边边的奇数）。特征二：左闭右开，left-1始终指向红色，right始终指向蓝色。

第二步，标准的左闭右开二分步骤。

注意：标准的二分模板会出现索引超范围问题，为了解决超限问题，可以在尾部添加一个不能取到的值。

3.解题代码

Python代码

class Solution:
    # 二分查找（红蓝染色法）
    # 第一步，确定红蓝染色的特征。特征一：红：位置i处值与处于同一对的元素相等；蓝：位置i处值与处于同一对的元素不相等（如果i为奇数，相邻元素取右边的偶数，反之取左边边的奇数）。特征二：左闭右开，left-1始终指向红色，right始终指向蓝色。
    # 第二步，标准的左闭右开二分步骤。
    # 注意：标准的二分模板会出现索引超范围问题，为了解决超限问题，可以在尾部添加一个不能取到的值。
    def singleNonDuplicate(self, nums: List[int]) -> int:
        # 红：i与相邻的对元素相等；蓝：i与相邻元素不相等（如果i为奇数，相邻元素取右边的偶数，反之取左边的奇数）。为了解决超限问题，在尾部添加一个哑结点
        length=len(nums)
        nums.append(-1)
        left,right=0,length
        while left<right:
            mid=(right-left)//2+left
            # neighIndex=mid+1 if mid%2==0 else mid-1
            neighIndex=mid^1
            if nums[mid]==nums[neighIndex]:
                left=mid+1
            else:
                right=mid
        return nums[left]

C++代码

class Solution {
public:
    int singleNonDuplicate(vector<int>& nums) {
        int length=nums.size();
        nums.push_back(-1);
        int left=0,right=length;
        while(left<right){
            int mid=(right-left)/2+left;
            int neighIndex=mid%2==0 ? mid+1 : mid-1;
            if(nums[mid]==nums[neighIndex]){
                left=mid+1;
            }else{
                right=mid;
            }
        }
        return nums[left];
    }
};

4.执行结果