1
,那么你要找到第二个1
是很麻烦的,为了方便比较这个数字是否唯一,首先要排序。其次,我们能发现排序后的规律,我们这样想:如果全部都是出现两次的数字,那形式就是类似aabbccdd
,那我们往里面加入一个单独的数字,就会变成像aabbeccdd
的情况,我们要找出e
,就可以通过每隔两个数进行遍历,如果不是单独数字,比如a
它的下一个一定是a
,若是单独数字,比如e
它的下一个就不相同了。所以我们通过遍历,只要找出那个唯一的单独数字,就可以直接输出,无需考虑后面的数字了。
还有一点我们需要注意数组长度,因为这道题给出的nums
一定是奇数(显而易见),通过遍历最后会剩下一个数,如果说前面的元素判断都是相同的,那么这个只出现一次的数就是这个在末尾的数。
时间复杂度:O(N)
class Solution:
def singleNumber(self, nums: List[int]) -> int:
nums.sort()
for i in range(0, len(nums)-1, 2):
if nums[i] != nums[i + 1]:
return nums[i]
return nums[-1] # 如果之前的遍历完,
第二种:纯数学方法。这道题我们可以通过数学计算方法来解,有两个思路:
第一个,我们通过set
方法将重复数字去掉并求和,然后和原列表之和相减,找出重复数字之和,因为重复次数为2
,那么我们把重复数字之和,用原列表的和来减去它,最后得到的就是那个只出现一次的数,可以用草稿纸举个例子,很好理解。
class Solution:
def singleNumber(self, nums: List[int]) -> int:
temp = sum(nums) - sum(set(nums))
return sum(nums) - temp * 2
第二个,我们将重复数字去掉后的数组求和并乘以2
,这样的话得到的这个数就是当nums
所有数字都是出现两次时的和,那么我们只需要减去原列表的和,就能轻松的到这个只出现一次的数了。
时间复杂度:O(N)
class Solution:
def singleNumber(self, nums: List[int]) -> int:
return sum(set(nums)) * 2 - sum(nums)
第三种:位运算法。这个方法我是一开始没想到的,确实很厉害。通过异或运算,这个运算有下面几个规律:
任何数字和 0 运算最后得到的还是这个数字。例如 A ⊙ 0 = A
。
任何数字和与他相同的数字运算得到的是 0 。例如 A ⊙ A = 0
。
异或运算满足交换律和结合律。
所以只需要我们从头开始遍历这个数组,将所有数都进行运算,就可以把相同的数都去除掉,最后剩下的数就是那个只出现一次的数字。
class Solution:
def singleNumber(self, nums: List[int]) -> int:
only_num = 0
for i in nums:
only_num ^= i
return only_num