LeetCode-singleNumber-只出現(xiàn)一次的數(shù)字

tinysun1234 發(fā)布于2019-07-30 16:06 / 2999人閱讀

摘要：描述給定一個(gè)整數(shù)數(shù)組，除了某個(gè)元素外其余元素均出現(xiàn)兩次。請(qǐng)找出這個(gè)只出現(xiàn)一次的元素。備注你的算法應(yīng)該是一個(gè)線性時(shí)間復(fù)雜度。

描述：

給定一個(gè)整數(shù)數(shù)組，除了某個(gè)元素外其余元素均出現(xiàn)兩次。請(qǐng)找出這個(gè)只出現(xiàn)一次的元素。

備注：

你的算法應(yīng)該是一個(gè)線性時(shí)間復(fù)雜度。你可以不用額外空間來實(shí)現(xiàn)它嗎？

實(shí)現(xiàn)：

#我的實(shí)現(xiàn)方法:利用count找出元素的個(gè)數(shù)，如果個(gè)數(shù)為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
但是這個(gè)方法的時(shí)間超時(shí)了，達(dá)不到題目的性能要求

可以利用Counter,可以將list轉(zhuǎn)化成，list里面的value對(duì)應(yīng)個(gè)數(shù)的字典
例如：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

樓下回復(fù)大神提示說可以先對(duì)list進(jìn)行排序：想到一種方法：排序之后進(jìn)行比較：

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]

根據(jù)大牛提示的每個(gè)元素異或的方式：
由于A XOR A = 0 且 ((A^A) ^ (B^B) ^ (C^C) ^ (D^D) ^ E) = ((0^ 0 ^ 0 ^ 0 ^ E) =E
直接把整個(gè)數(shù)組異或運(yùn)算，最后的出來的就是只出現(xiàn)一次的數(shù)字了。

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