题目

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

说明:

你的算法应该具有线性时间复杂度。 你可以不使用额外空间来实现吗?

示例 1:

输入: [2,2,1]
输出: 1

示例 2:

输入: [4,1,2,1,2]
输出: 4

解答

  1. 思路

    • 使用空间代换

      • 用 set 过滤一次,遍历原有数组,如果存在则移除 set 中数据,最后留存数据

      • 使用 dict(map)记录,然后统计 values

    • 不适用空间代换

      • 异或运算的运用,案例如下:

        案例
        1
        2
        3
        4
        5
        6
        7
        8
        9
        10
        11
        12
        13
        14
        15
        16
        17
        18
        19
        20
        # 原始数据
        xor = 0
        nums = [2, 2, 4, 3, 4]
        # 异或运算过程
        0 0 0 0 = xor = 0
        0 0 1 0 = nums[0] = 2
        -------
        0 0 1 0 = 2
        0 0 1 0 = nums[1] = 2
        -------
        0 0 0 0 = 0
        0 1 0 0 = nums[2] = 4
        -------
        0 1 0 0 = 4
        0 0 1 1 = nums[3] = 3
        -------
        0 1 1 1 = 7
        0 1 0 0 = nums[4] = 4
        -------
        0 0 1 1 = 3
  2. 代码

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    class Solution:
    def singleNumber(self, nums: List[int]) -> int:
    xor = 0
    for i in range(len(nums)):
    xor ^= nums[i]
    return xor

    if __name__ == '__main__':
    nums = [2, 2, 4, 3, 4]
    print(Solution().singleNumber(nums))

写在最后

版本内容时间
v1.0.01. 初始化文档2020-01-15 17:40:17