[刷题]Leetcode-136:Single Number(只出现一次的数字)

原文链接:[刷题]Leetcode-136:Single Number(只出现一次的数字) - 高歌的博客

题目详情

题目描述:
给定一个非空整数数组,除了某个元素只出现一次以外,其余每个元素均出现两次。找出那个只出现了一次的元素。
说明:
你的算法应该具有线性时间复杂度。 你可以不使用额外空间来实现吗?
示例 1:
输入: [2,2,1]
输出: 1
示例 2:
输入: [4,1,2,1,2]
输出: 4
class Solution:
    def singleNumber(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """

解题思路

首先想到了用暴力搜索的方式,新建一个s list,对nums中的元素逐一迭代,判断元素是否在s中,如果s存在迭代的元素,则否定该元素,直到找到唯一的数字,这个思路最容易想到,代码也很容易写出就不展示了,但是最后结果肯定是超时,因为题目的考察重点不在于此。同样用python自带的list.count(i)的方式也会超时,因为本质上还是在暴力搜索。

因为只有一个元素是出现一次的,很容易想到了异或运算,二进制位相同为0相异为1,这样可以用一个变量做筛选,只需要len(nums)次异或运算就能找到结果,尝试解题方案如下:

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

通过,耗时在100ms之内,翻看其他人的解体方案,一个很巧妙的方案:

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

因为只有一个元素出现一次,直接set去重求2倍和,然后和nums的和相减直接get目标,nice!

©著作权归作者所有,转载或内容合作请联系作者
【社区内容提示】社区部分内容疑似由AI辅助生成,浏览时请结合常识与多方信息审慎甄别。
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。

相关阅读更多精彩内容

  • <center>#1 Two Sum</center> link Description:Given an arr...
    铛铛铛clark阅读 2,450评论 0赞 3
  • 背景 一年多以前我在知乎上答了有关LeetCode的问题, 分享了一些自己做题目的经验。 张土汪:刷leetcod...
    土汪阅读 13,154评论 0赞 33
  • 本文内容为练习LeetCode题目时的解题思路和不同算法的记录,实现语言为C++,代码保存在Github,均已在L...
    SK木眠阅读 1,182评论 0赞 0
  • LeetCode 刷题随手记 - 第一部分 前 256 题(非会员),仅算法题,的吐槽 https://leetc...
    蕾娜漢默阅读 18,561评论 2赞 36
  • 秋 抵挡不住风的吹袭 把芬芳和美挂在季节深处 飘摇的荻花 映日的红柿 是牵引你的帆和灯盏 篱畔的秋菊 山颠的寒树 ...
    最爱微风草动摇阅读 339评论 1赞 4

友情链接更多精彩内容