40.数组中只出现一次的数字
一个整型数组里除了两个数字之外，其他的数字都出现了两次。写出这两个只出现了一次的数字。时间复杂度为O(n)，空间复杂度为O(1)。
Leetcode 540.Single Element in a Sorted Array
You are given a sorted array consisting of only integers where every element appears exactly twice, except for one element which appears exactly once. Find this single element that appears only once.
给定一个整型排序数组，除了一个数字只出现一次，其他数字均出现两次。找出该数字。
Example 1
Input: [1,1,2,3,3,4,4,8,8]
Output: 2
Example 2
Input: [3,3,7,7,10,11,11]
Output: 10
方法一：
遍历列表，并给元素计数，输出计数为1的元素。
代码：
class Solution:
def singleNonDuplicate(self, nums: List[int]) -> int:
for i in range(len(nums)):
num = nums.count(nums[i])
if num == 1:
return nums[i]
结果：
Runtime: 6580 ms, faster than 5.29% of Python3 online submissions for Single Element in a Sorted Array.
Memory Usage: 15 MB, less than 7.69% of Python3 online submissions for Single Element in a Sorted Array.
方法二：
由于列表元素要么出现一次，要么两次。于是可将列表逆序遍历。
对某一元素，将其从列表中删除后，查看它(tmp)在列表中是否还存在。若存在，将其删除，列表长度减2；若不存在，返回该值。
代码：
class Solution:
def singleNonDuplicate(self, nums: List[int]) -> int:
i = len(nums) - 1
while i >= 0:
tmp = nums[i]
nums.pop(i)
if tmp in nums:
nums.pop(nums.index(tmp))
i -= 2
else:
return tmp
结果:
Runtime: 1944 ms, faster than 5.29% of Python3 online submissions for Single Element in a Sorted Array.
Memory Usage: 14.8 MB, less than 7.69% of Python3 online submissions for Single Element in a Sorted Array.
方法三：(推荐)
由于数组元素按照升序排列，所以分四种情况。
1.若数组长度为1，则直接返回该元素；
2.若目标元素在表头，则当它不等于其后元素时，返回；
3.若目标元素在表末，当它不等于其前面元素时，返回；
4.目标元素在表中，当它不等于它前一个元素也不等于它后一个元素时，返回。
代码：
class Solution:
def singleNonDuplicate(self, nums: List[int]) -> int:
if len(nums) == 1:
return nums[0]
if nums[0] != nums[1]:
return nums[0]
if nums[-1] != nums[-2]:
return nums[-1]
for i in range(1, len(nums)-1):
if nums[i] != nums[i-1] and nums[i] != nums[i+1]:
return nums[i]
结果：
Runtime: 68 ms, faster than 90.01% of Python3 online submissions for Single Element in a Sorted Array.
Memory Usage: 15 MB, less than 7.69% of Python3 online submissions for Single Element in a Sorted Array.