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

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

最后

以上就是热情衬衫为你收集整理的day24(力扣)只出现一次的数字(python实现)的全部内容，希望文章能够帮你解决day24(力扣)只出现一次的数字(python实现)所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。