LeetCode-singleNumber-只出现一次的数字

tinysun1234 发布于2019-07-30 16:06 / 2989人阅读

摘要：描述给定一个整数数组，除了某个元素外其余元素均出现两次。请找出这个只出现一次的元素。备注你的算法应该是一个线性时间复杂度。

描述：

给定一个整数数组，除了某个元素外其余元素均出现两次。请找出这个只出现一次的元素。

备注：

你的算法应该是一个线性时间复杂度。你可以不用额外空间来实现它吗？

实现：

#我的实现方法:利用count找出元素的个数，如果个数为1的就是要找的
class Solution(object):
    def singleNumber(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        for i in nums:
            n  = nums.count(i)
            if n ==1:
                return i
但是这个方法的时间超时了，达不到题目的性能要求

可以利用Counter,可以将list转化成，list里面的value对应个数的字典
例如：numss = [2,2,1,1,1,3]
{1: 3, 2: 2, 3: 1}

from collections import Counter


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

楼下回复大神提示说可以先对list进行排序：想到一种方法：排序之后进行比较：

class Solution(object):
    def singleNumber(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        nums.sort()
        
        if len(nums)==1:
            return nums[0]
        else:  
            if nums[0] != nums[1]:
                return nums[0]

            elif nums[len(nums) - 1] != nums[len(nums) - 2]:
                return nums[len(nums) - 1]



            else:
                for n in range(len(nums)):
                    if nums[n + 2] != nums[n + 1] and nums[n+2] != nums[n+3]:
                        return nums[n + 2]

根据大牛提示的每个元素异或的方式：
由于A XOR A = 0 且 ((A^A) ^ (B^B) ^ (C^C) ^ (D^D) ^ E) = ((0^ 0 ^ 0 ^ 0 ^ E) =E
直接把整个数组异或运算，最后的出来的就是只出现一次的数字了。

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

云服务器 GPU云服务器最近一次的登录时间只显示一次代码只执行一次 asp只刷新一次

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/41481.html

一道有意思的面试算法题

摘要：解决方案异或操作异或运算是对于二进制数字而言的，比如说一个有两个二进制，如果两个值不相同，则异或结果为。比如说，本质上其实是和的每一对比特位执行异或操作，等价于下面数字对应的二进制数字对应的二进制数字对应的二进制因此的结果就为啦。新年第一篇文章，先祝大家新年快乐！！那么接下来进入正文。前言前阵子突发奇想，突然开始刷leetcode。其中刷到了一道有意思的题目，发现这道题是当时秋招...

maxmin 2019-08-23 14:28 评论0 收藏0
由三道 LeetCode 题目简单了解一下位运算

摘要：使用位运算数组只出现一次数字的数组得到最低的有效位，即两个数不同的那一位看完上面的解法，我脑海中只有问号的存在，啥意思啊下面就让我们简单了解一下位运算并解析一下这三道题目。另，负数按补码形式参加按位与运算。你可做过这几道题？在面试的准备过程中，刷算法题算是必修课，当然我也不例外。某天，我刷到了一道神奇的题目： # 136. 只出现一次的数字给定一个非空整数数组，除了某个元素只出现一次以外...

daydream 2019-05-21 11:41 评论0 收藏0
由三道 LeetCode 题目简单了解一下位运算

摘要：简单介绍一下位运算异或运算异或逻辑的关系是当不同时，输出当相同时，输出。另，负数按补码形式参加按位与运算。使一个数的最低位为零，可以表示为。，截止到这儿，三道题目中使用的位运算介绍完毕，那么这里我们插入一下的详细题解。你可做过这几道题？在面试的准备过程中，刷算法题算是必修课，当然我也不例外。某天，我刷到了一道神奇的题目： # 136. 只出现一次的数字给定一个非空整数数组，除了某个元素只...

刘明 2019-05-22 14:21 评论0 收藏0
【刷算法】LeetCode.136-只出现一次的数字

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

DataPipeline 2019-08-23 11:48 评论0 收藏0
leetcode137. Single Number II

摘要：按照思路一和思路二很容易将这题解决。在这里，我们希望将出现三次的数字通过操作划掉。之后，我们使用和分别来记录第一位和第二位的情况。最后只出现一次的数值应该是保存在中，换句话说，最后应该全是。题目要求 Given an array of integers, every element appears three times except for one, which appears e...

mochixuan 2019-08-15 11:12 评论0 收藏0