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

  【前言】坚持日更LeetCode刷题系列    不积跬步,无以至千里;不积小流,无以成江海。愿与诸君共勉！   【题目】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]

   关于其中一些知识的链接：   

   注明：