美文网首页
寻找落单数

寻找落单数

作者: 拔丝圣代 | 来源:发表于2018-02-13 09:22 被阅读0次

题目


给一个整数数组,其中除了只有一个数只出现一次以外,其他每一个数都出现两次。找出这个数。
注意:能否不使用额外空间?

解法


思路1 集合

遍历数组,用一个集合保存出现过1次的元素,若出现第二次则删除,最后集合剩下的一个值即为所求。

class Solution(object):
    def singleNumber(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        l = set([])
        for i in nums:
            if i not in l:
                l.add(i)
            else:
                l.discard(i)
        return l.pop()

思路2 求差

2∗(a+b+c)−(a+a+b+b+c)=c
用代码表示即为
2 * sum(set(nums)) - sum(nums)

思路3 异或 (原地算法)

所有数进行异或,即得所求

class Solution(object):
    def singleNumber(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        a = 0
        for i in nums:
            a ^= i
        return a

相关文章

  • 寻找落单数

    题目 给一个整数数组,其中除了只有一个数只出现一次以外,其他每一个数都出现两次。找出这个数。注意:能否不使用额外空...

  • Single Number寻找单数

    Easy, bit manipulation 给定整数序列,其中除了一个数其他数都出现两次,找出该单数。复杂度O(...

  • 寻找落鲸岛

    今天是七月五号,传说中落鲸岛出现的日子。 一大早,于小小就醒过来了。这是她寻找落鲸岛的第五年了,今年她一定要找到落...

  • 单数

    音节单调响起钢琴键的黑白翩翩起舞,成双成对旋转是双数的美 秋叶落霞舞鞋,枯叶上人们舞蹈,痴迷的笑黄昏遮挡不住白裙流...

  • 单数

    我站在时光的站台上 掐着指腹 秒针上一直有雾 好像时间来自雾的深处 横跨在田埂上的老路 垄在东 沟在西 我 二十一

  • 收集表单数据

    收集表单数据