难度: Medium
给定一个只包含整数的有序数组 nums ，每个元素都会出现两次，唯有一个数只会出现一次，请找出这个唯一的数字。
示例 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 <= 1050 <= nums[i] <= 105进阶: 采用的方案可以在 O(log n) 时间复杂度和 O(1) 空间复杂度中运行吗？
注意：本题与主站 540 题相同：https://leetcode-cn.com/problems/single-element-in-a-sorted-array/
运行时间: 22 ms
内存: 17.9 MB
class Solution:
def singleNonDuplicate(self, nums: List[int]) -> int:
# 双指针
n = len(nums)
left = 0
while left<n-1:
if nums[left]==nums[left+1]:
left+=2
else:
return nums[left]
return nums[-1]
题解采用了一种扫描方式来查找唯一不重复的元素。由于数组是有序的，并且除了一个唯一的元素外，其他元素都出现两次，算法利用这个特性来跳过成对的元素。具体方法是使用一个指针（left），从数组的开始遍历，每次检查left指针和其相邻元素left+1。如果这两个元素相等，说明它们是一对，因此left指针跳过这两个元素，即left增加2。如果这两个元素不等，说明当前left指向的元素是唯一的不重复元素，直接返回该元素。如果整个数组都被遍历完，最后一个元素是唯一不重复的元素。
时间复杂度: O(n)
空间复杂度: O(1)
class Solution:
def singleNonDuplicate(self, nums: List[int]) -> int:
# 初始化数组长度
n = len(nums)
# 初始化左指针
left = 0
# 当左指针还未达到数组末尾时进行循环
while left < n - 1:
# 如果左指针和右边的元素相等，则跳过这一对元素，移动两步
if nums[left] == nums[left + 1]:
left += 2
else:
# 如果不相等，说明左指针指向的元素是唯一的不重复元素
return nums[left]
# 如果所有元素都成对出现，返回数组的最后一个元素
return nums[-1]
算法基于的假设是数组是有序的，并且除了一个唯一的元素以外，其他所有元素都恰好出现两次。因此，当我们按照步长为2遍历数组时，正常情况下每对相邻的元素应该是相同的。如果在某一步中，left指针指向的元素与其相邻元素不相等，这意味着从数组开始到当前left指针的位置，所有元素都是成对出现的。因此，当前left指向的元素必然是唯一的不重复元素，没有其它元素与之配对，可以直接返回此元素作为结果。
在这种情况下，当left指针从数组的开始逐步以2的步长增加时，它会成功地跳过所有成对的元素。由于所有成对的元素都被正确处理，left指针最终会指向数组的最后一个元素。此时，由于left指针已经超出了成对元素的范围，而且根据问题设定，最后一个元素是唯一不重复的，因此算法会在最后一次循环中返回这个元素。
在算法的设计中，循环的条件是left < n - 1，这确保了只要left未达到数组末尾前的最后一个元素，循环就会继续执行。如果所有之前的元素都成对出现了，那么left指针会最终停在数组的最后一个元素上。在循环结束时，如果left指向的是最后一个元素，根据循环的退出条件，我们知道这个元素未能与前一个元素形成一对，因此它就是唯一的不重复元素，算法会返回这个最后一个元素。