成人国产在线小视频_日韩寡妇人妻调教在线播放_色成人www永久在线观看_2018国产精品久久_亚洲欧美高清在线30p_亚洲少妇综合一区_黄色在线播放国产_亚洲另类技巧小说校园_国产主播xx日韩_a级毛片在线免费

資訊專欄INFORMATION COLUMN

268. Missing Number

Steven / 2789人閱讀

摘要：之后我們可以查看頭尾兩個數(shù)字是否符合要求。如果不符合我們可以直接返回結(jié)果。方法利用的特點。方法求和根據(jù)高斯定理，從到的和為。所以把數(shù)組的所有數(shù)字求和，然后與從到的和相減所得數(shù)字，就是我們需要的數(shù)字。

題目鏈接：Missing Number

思路：
方法1: 排序
我們很自然的可以想到，如果數(shù)組是排好序的，那么可以很容易的找到缺少的數(shù)字。
之后我們可以查看頭尾兩個數(shù)字是否符合要求。如果不符合我們可以直接返回結(jié)果。
最后，我們查從1到n-1個數(shù)字。

方法2: Bit Manipulation
利用“XOR”的特點。比如 1 XOR 1 = 0，但1 XOR 1 XOR 2 = 2。
所以只要把數(shù)組中的數(shù)字和數(shù)組中的index全部XOR，那么缺少的那個肯定是我們需要的數(shù)字。

方法3: HashSet
放數(shù)組的數(shù)字放到HashSet里面，然后遍歷這個HashSet。如果數(shù)字不在就說明這是我們要找的數(shù)字。

方法4: 求和
根據(jù)高斯定理，從1到n的和為 ((1+n) * n)/2。
所以把數(shù)組的所有數(shù)字求和，然后與從1到n的和相減所得數(shù)字，就是我們需要的數(shù)字。

時間復(fù)雜度：
方法1:

時間：O(nlogn) 
空間：O(1) if we sort the numbers in place

方法2:

時間：O(n)
空間：O(1)

方法3:

時間：O(n)
空間：O(n)

方法4:

時間：O(n)
空間：O(1)

代碼：

方法1：

class Solution(object):
    def missingNumber(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        nums.sort()
        if nums[0] != 0:
            return 0
        if nums[-1] != len(nums):
            return len(nums)
        
        for i in range(1, len(nums)):
            exp_val = nums[i-1] + 1
            if nums[i] != exp_val:
                return exp_val

方法2:

class Solution(object):
    def missingNumber(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        res = len(nums)
        for i, num in enumerate(nums):
            res ^= i ^ num
        return res

方法3:

class Solution(object):
    def missingNumber(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        nums = set(nums)
        n = len(nums) + 1
        for i in range(n):
            if i not in nums:
                return i

方法4:

class Solution(object):
    def missingNumber(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        exp_sum = len(nums) * (len(nums) + 1) // 2
        sum_n = sum(nums)
        return exp_sum - sum_n

文章版權(quán)歸作者所有，未經(jīng)允許請勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。

轉(zhuǎn)載請注明本文地址：http://systransis.cn/yun/41961.html

相關(guān)文章

  • 268. Missing Number

    摘要：題目解答一開始我的思始很簡單，排序，查找但是可以用的方法，因為只有一個，所以可以把其它所有的數(shù)都配好對，剩下這個就是我們要找的這里很喔，因為只少了一個數(shù)，舉個例子所以當(dāng)我們把這些數(shù)的時候，唯一一個剩下的就是的這個數(shù) 題目：Given an array containing n distinct numbers taken from 0, 1, 2, ..., n, find the o...

    NSFish 評論0 收藏0

  • leetcode 268 Missing Number

    摘要：題目詳情題目的意思是輸入一個長度為的數(shù)組，找到這個數(shù)字中不存在于數(shù)組中的丟失的數(shù)字思路我的想法是，用這個數(shù)的和減去數(shù)組中的每一個元素的值，最后剩下的值就是丟失的數(shù)字解法 題目詳情 Given an array containing n distinct numbers taken from 0, 1, 2, ..., n, find the one that is missing fr...

    tianyu 評論0 收藏0

  • leetcode 部分解答索引（持續(xù)更新～）

    摘要：前言從開始寫相關(guān)的博客到現(xiàn)在也蠻多篇了。而且當(dāng)時也沒有按順序?qū)懍F(xiàn)在翻起來覺得蠻亂的?？赡艽蠹铱粗卜浅２环奖?。所以在這里做個索引嘻嘻。順序整理更新更新更新更新更新更新更新更新更新更新更新更新更新更新更新更新 前言 從開始寫leetcode相關(guān)的博客到現(xiàn)在也蠻多篇了。而且當(dāng)時也沒有按順序?qū)憽F(xiàn)在翻起來覺得蠻亂的?？赡艽蠹铱粗卜浅２环奖恪Ｋ栽谶@里做個索引嘻嘻。 順序整理 1~50 1...

    leo108 評論0 收藏0

  • LeetCode偶爾一題 —— 268. 缺失數(shù)字

    摘要：題目描述給定一個包含中個數(shù)的序列，找出中沒有出現(xiàn)在序列中的那個數(shù)。示例輸入輸出示例輸入輸出最簡單的解法剛看到的這道題的時候，第一感覺就是排序，之后直接挨個比較就能找到缺失的數(shù)字。 題目描述 給定一個包含 0, 1, 2, ..., n 中 n 個數(shù)的序列，找出 0 .. n 中沒有出現(xiàn)在序列中的那個數(shù)。 示例 1: 輸入: [3,0,1] 輸出: 2 示例 2: 輸入: [9,6,...

    e10101 評論0 收藏0

  • 前端 | 每天一個 LeetCode

    摘要：在線網(wǎng)站地址我的微信公眾號完整題目列表從年月日起，每天更新一題，順序從易到難，目前已更新個題。這是項目地址歡迎一起交流學(xué)習(xí)。 這篇文章記錄我練習(xí)的 LeetCode 題目，語言 JavaScript。 在線網(wǎng)站：https://cattle.w3fun.com GitHub 地址：https://github.com/swpuLeo/ca...我的微信公眾號： showImg(htt...

    張漢慶 評論0 收藏0

發(fā)表評論

0條評論

最新活動
閱讀需要支付1元查看
<