day24(力扣)只出现一次的数字(python实现)

野性酷女 2021-10-30 01:16 161阅读 0赞

题目描述：给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。  
说明：你的算法应该具有线性时间复杂度。 你可以不使用额外空间来实现吗？  
示例 1:

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

示例 2:

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

分析：首先想到的可以是采用**暴力法**（两次无脑循环）进行解决，但是很显然，这个方法的时间复杂度达到了平方级，因此并不可取。其次，我们可以考虑**哈希**，具体步骤为：如果元素第一次出现，直接插入哈希表；如果是第二次出现，删除哈希集中的元素；最后剩下的那个元素就是只出现过一次的元素。哈希集有个重要特性，其是**不包含任何重复元素的无序集合**。所以，对于此题是很适用的。

class Solution(object):
        def singleNumber(self, nums):
            """
            :type nums: List[int]
            :rtype: int
            """
            hash_table = {}
            for i in nums:
                try:
                    hash_table.pop(i)       #如果存在，就删除
                except:
                    hash_table[i] = 1       #不存在就添加进哈希表
            return hash_table.popitem()[0]

**数学法**：小编在做完之后随手看了一下官方的题解，发现了一个很有心计的解法，原理就是一个数学公式：`2∗(a+b+c)−(a+a+b+b+c)=c`，实现起来自然很简单。

class Solution(object):
        def singleNumber(self, nums):
            """
            :type nums: List[int]
            :rtype: int
            """
            return 2 * sum(set(nums)) - sum(nums)