LeetCode-singleNumber-只出現一次的數字

tinysun1234 發布于2019-07-30 16:06 / 2990人閱讀

摘要：描述給定一個整數數組，除了某個元素外其余元素均出現兩次。請找出這個只出現一次的元素。備注你的算法應該是一個線性時間復雜度。

描述：

給定一個整數數組，除了某個元素外其余元素均出現兩次。請找出這個只出現一次的元素。

備注：

你的算法應該是一個線性時間復雜度。你可以不用額外空間來實現它嗎？

實現：

#我的實現方法:利用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只刷新一次

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://specialneedsforspecialkids.com/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