「只出现一次的数字」python之leetcode刷题|007

作者 : 开心源码 本文共905个字,预计阅读时间需要3分钟 发布时间: 2022-05-13 共291人阅读

题目

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

说明:
你的算法应该具备线性时间复杂度。 你可以不使用额外空间来实现吗?

示例 1:

输入: [2,2,3,2]
输出: 3
示例 2:
输入: [0,1,0,1,0,1,99]
输出: 99

解答

这道题是中等难度的题目,刚开始我一看,哎,这么简单,顺手就写了起来

class Solution(object):    def singleNumber(self, nums):        """        :type nums: List[int]        :rtype: int        """        for i in nums:            if nums.count(i) == 1:                return i

运行一看也正确,没啥问题,统计数字嘛,以前也遇见过。
可是当我看运行结果我才知道,这道题不是不仅仅是解出来结果就行了。还要考虑时间复杂度。
看一下我的运行结果

执行结果

可以看到只打败了10%的提交者,尽管处理了问题,可耗时太长,显然不是这道题的最好处理方法。
看看大佬的代码

class Solution(object):    def singleNumber(self, nums):        """        :type nums: List[int]        :rtype: int        """        if len(nums) == 1:            return nums[0]        a = sorted(nums)        for i in range(0,len(nums)-1):            if a[i] == a[i-1] or a[i] == a[i+1]:                continue            else:                return a[i]        return a[-1]

之所以我的代码耗时时间长,是由于每次统计都要遍历一遍列表,大佬的代码只遍历了一次。
再看一个

class Solution(object):    def singleNumber(self, nums):        """        :type nums: List[int]        :rtype: int        """        buffer_dict = {x: 0 for x in nums}        for x in nums:            buffer_dict[x] += 1        for x in buffer_dict.items():            if x[1] == 1:                return x[0]

利用字典来做,时间复杂度最小,耗时28ms,目前来说最好的处理方法。

说明
1. 本站所有资源来源于用户上传和网络,如有侵权请邮件联系站长!
2. 分享目的仅供大家学习和交流,您必须在下载后24小时内删除!
3. 不得使用于非法商业用途,不得违反国家法律。否则后果自负!
4. 本站提供的源码、模板、插件等等其他资源,都不包含技术服务请大家谅解!
5. 如有链接无法下载、失效或广告,请联系管理员处理!
6. 本站资源售价只是摆设,本站源码仅提供给会员学习使用!
7. 如遇到加密压缩包,请使用360解压,如遇到无法解压的请联系管理员
开心源码网 » 「只出现一次的数字」python之leetcode刷题|007

发表回复