题目

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

说明：

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

示例 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