540 有序数组中的单一元素（找规律、二分查找）

「爱情、让人受尽委屈。」 2022-08-31 01:56 168阅读 0赞

**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  
进阶: 采用的方案可以在 O(log n) 时间复杂度和 O(1) 空间复杂度中运行吗？  
来源：力扣（LeetCode）  
链接：https://leetcode-cn.com/problems/single-element-in-a-sorted-array

**2. 思路分析：**

最简单的做法是将所有元素异或起来那么所有元素异或的结果就是答案（相同的元素异或之后结果为0，不同元素的异或结果为1），但是因为这个数组是有序的所以题目要求我们使用logn的算法实现，也即我们需要使用其他的方法解决。时间复杂度为O(logn)的算法一般有**二分查找**，我们需要先找一下其中的规律，因为数组元素为奇数所以我们可以添加一个数字使得可以两两分组，可以发现两两分组之后可以分为两部分，左边是所有组内元素都是相等的，右边是所有组内元素都是不相等的，答案就是在分界点的第一个元素，所以我们根据这个规律二分即可。

**3. 代码如下：**

from typing import List
    
    
    class Solution:
        def singleNonDuplicate(self, nums: List[int]) -> int:
            # 先在最后添加一个数字, 只要与最后一个数字不相等即可
            nums.append(nums[-1] + 1)
            # 二分的是每一个组判断组内元素是否相等
            l, r = 0, len(nums) // 2 - 1
            while l < r:
                mid = l + r >> 1
                # 当前的组内元素不相等说明答案应该是当前的位置或者在左边
                if nums[2 * mid] != nums[2 * mid + 1]: r = mid
                else:l = mid + 1
            return nums[2 * r]