LeeCode每日一题--只出现一次的数字

Beth ·

更新时间:2024-09-21

· 984 次阅读

【前言】坚持日更LeeCode刷题系列
不积跬步,无以至千里;不积小流,无以成江海。愿与诸君共勉！

【题目】136.只出现一次的数字
题目描述：给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。

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

示例:

		示例 1:
			输入: [2,2,1]
			输出: 1
		示例 2:
			输入: [4,1,2,1,2]
			输出: 4

思路一:虽然知道暴力法会出现超时错误，但是根据某位前辈所说，往往暴力求解是我们最容易想到的方法，而在这基础上我们也可以更好的去思考如何改进算法。所以我还是实现了一下暴力求解的方式。
思路为通过两个循环的遍历，来统计每个元素出现的次数，如果大于等于2，则跳出循环；如果等于1并且已经遍历到了最后一个元素，则返回那个值。具体代码如下：

class Solution(object):
    def singleNumber(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        if len(nums)==1:
            return nums[0]
        else:
            for i in range(len(nums)):
                count = 0   #这里设为0是因为在下面的比较过程中，也比较了自己本身那个元素
                for j in range(len(nums)):
                    if nums[i] == nums[j]:
                        count = count+1
                    if count>=2:  #大于等于2则跳出循环
                        break
                    elif count==1 and j == len(nums)-1:#等于1且遍历到了最后一个元素
                        return nums[i]

运行结果：出现了超时错误，采用两层循环的方式，时间复杂度为O(n^2)，因此对于过长的列表时，会出现超时的现象。

  思路二:那么我们怎么优化呢？？？我们可以思考下上面做法中为什么需要两次循环？
      相信对上面方法没有问题的朋友可以很快回答出：第一个循环是遍历所有的元素，第二个循环是为了计数。
      接下来的问题就成了我们如何将这两步尽可能的缩减，具体步骤如下：
      1.采用字典的方式来进行存储，因为它可以在遍历的时候完成计数的功能
      2.关于计数，因为题目给出的是只有一个出现一次，其他均出现两次，那么很好，我们只需要对没有存在于字典的元素赋值为1，已存在的元素赋值为2
      3.遍历字典的所有键，返回值为1的index
      具体代码如下：

class Solution(object):
    def singleNumber(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        hashmap = {}  #用于存储
        for index,num in enumerate(nums):
            if num not in hashmap:  #如果该元素未在hashmap中
                hashmap[num] = 1
            elif num in hashmap:   #如果该元素在hashmap中
                hashmap[num] = 2
        for i in list(dict.keys(hashmap)): #循环遍历hashmap的键
            if hashmap[i] ==1:
                return i

运行结果：
在这里插入图片描述

思路三:当然我们也很容易的想到使用列表中的count函数来统计数字个数，具体代码如下：

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

运行结果：