题目

给你一个 非空 整数数组 nums ，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。

你必须设计并实现线性时间复杂度的算法来解决此问题，且该算法只使用常量额外空间。

示例 1 ：

**输入：**nums = [2,2,1]

**输出：1

示例 2 ：

**输入：**nums = [4,1,2,1,2]

**输出：4

示例 3 ：

**输入：**nums = [1]

**输出：1

提示：

  • 1 <= nums.length <= 3 * 104
  • -3 * 104 <= nums[i] <= 3 * 104
  • 除了某个元素只出现一次以外，其余每个元素均出现两次。

题解

官方题解

Python

官方的题解是使用异或方法，相同数字进行异或运算得到的结果是 0，0 和任何数进行异或运算的结果是该数字，那么只要对所有数进行异或运算就可以得到结果了。

1
class Solution: def singleNumber(self, nums: List[int]) -> int: return reduce(lambda x, y: x ^ y, nums)

我的题解

Python

思路比较朴素，就是先对整个序列进行一次排序，然后从头到尾进行遍历，对于每个偶数位置 i，如果 nums[i] != nums[i + 1]，就说明有一个单独的数了，这个适合需要 return nums[i]，如果遍历到最后，都没有这种情况，那么有两张情况：

1）没有单独的数，万事大吉了~

2）最后一个是单独的数，需要单独判断 nums[len_num - 2] != nums[len_num -1]，不等就返回最后一个数就好啦~

当然还有一个很特殊的情况：数组只有一个元素的时候，直接 return nums[0]~

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution:
    def singleNumber(self, nums: List[int]) -> int:
        # 先对数组进行排序
        nums.sort()
        len_num = len(nums)
        i = 0
        # 如果只有一个元素，直接 return
        if len_num == 1:
            return nums[0]
        # 如果偶数位置出现不等的情况，返回该位置
        while i < len_num - 1:
            if nums[i] != nums[i + 1]:
                return nums[i]
            i = i + 2
        # 遍历完成有两种情况需要额外考虑，最后是否是单独的
        if nums[len_num - 2] != nums[len_num - 1]:
            return nums[len_num - 1]

运行结果

image.png