41. 缺失的第一個正數(shù)

enali 發(fā)布于2019-07-30 18:37 / 832人閱讀

摘要：問題問題描述給定一個未排序的整數(shù)數(shù)組，找出其中沒有出現(xiàn)的最小的正整數(shù)。原因就在于使用的內(nèi)置的函數(shù)的復(fù)雜度超過的比如的復(fù)雜度就是。

問題 問題描述

給定一個未排序的整數(shù)數(shù)組，找出其中沒有出現(xiàn)的最小的正整數(shù)。

說明

你的算法的時(shí)間復(fù)雜度應(yīng)為O(n)，并且只能使用常數(shù)級別的空間。

解答

首先因?yàn)橹荒苁褂贸?shù)級別的空間，就不能再建新的O(n)級的list，set等。然后就想到將列表去重去除非正數(shù)排序，最后循環(huán)當(dāng)nums[i]和(i+1)不等是輸出。

class Solution:
    def firstMissingPositive(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        nums = list(set([i for i in nums if i > 0]))
        nums.sort()
        for i in range(len(nums)):
            if nums[i] != i + 1:
                return i + 1
        return len(nums) + 1

但是這樣寫并不正確。原因就在于使用的Python內(nèi)置的函數(shù)的復(fù)雜度超過的O(n), 比如sort()的復(fù)雜度就是O(nlogn)。詳細(xì)資料可以參考Python內(nèi)置函數(shù)時(shí)間復(fù)雜度

經(jīng)過思考，只需要將列表中在列表長度范圍內(nèi)的正整數(shù)n移動到列表(n-1)的位置，然后再循環(huán)當(dāng)nums[i]和(i+1)不等是輸出。

class Solution:
    def firstMissingPositive(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        k = len(nums)
        if k == 0:
            return 1
        for i in range(k):
            while 0 < nums[i] <= k and nums[i] != nums[nums[i] - 1]:
                a = nums[nums[i] - 1]
                nums[nums[i] - 1] = nums[i]
                nums[i] = a
        for i in range(k):
            if nums[i] != i + 1:
                return i+1
        return k + 1

GPU云服務(wù)器云服務(wù)器事件 41 Discuz41 android41 mysql 5.0.41

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

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

相關(guān)文章

LeetCode 之 JavaScript 解答第41題 —— 缺失的第一個正數(shù)（First Mis

摘要：小鹿題目算法思路桶排序思想。再遍歷數(shù)組，從下標(biāo)開始判斷該下標(biāo)是否存放規(guī)定的數(shù)據(jù)，如果不是則該下標(biāo)就是這組數(shù)據(jù)中缺失的最小正整數(shù)。桶排序還可以實(shí)現(xiàn)在一組數(shù)據(jù)中查找重復(fù)的數(shù)據(jù)。 Time：2019/4/6Title: First Missing PositiveDifficulty: DifficultyAuthor: 小鹿題目：First Missing Positive Give...

levius 2019-08-23 16:46 評論0 收藏0
LeetCode41.缺失的第一個正數(shù) JavaScript

摘要：給定一個未排序的整數(shù)數(shù)組，找出其中沒有出現(xiàn)的最小的正整數(shù)。示例輸入輸出示例輸入輸出示例輸入輸出答案參考給定一個未排序的整數(shù)數(shù)組，找出其中沒有出現(xiàn)的最小的正整數(shù)。示例 1: 輸入: [1,2,0]輸出: 3 示例 2: 輸入: [3,4,-1,1]輸出: 2 示例 3: 輸入: [7,8,9,11,12]輸出: 1 答案參考： /** * @param {number[]} num...

ymyang 2019-08-23 15:17 評論0 收藏0
6-9月技術(shù)文章匯總

摘要：分布式的管理和當(dāng)我在談?wù)摷軜?gòu)時(shí)我在談啥狀態(tài)碼詳解無狀態(tài)協(xié)議和請求支持哪些方法分層協(xié)議棧有哪些數(shù)據(jù)結(jié)構(gòu)運(yùn)用場景說說你常用的命令為什么要有包裝類面向?qū)ο蟮奶卣魇巧妒巧队惺裁春锰幭到y(tǒng)設(shè)計(jì)工程在線診斷系統(tǒng)設(shè)計(jì)與實(shí)現(xiàn)索引背后的數(shù)據(jù)結(jié)構(gòu)及算法原理軟技能 HTTP 【HTTP】分布式session的管理【HTTP】Cookie和Session 【HTTP】當(dāng)我在談?wù)揜estFul架構(gòu)時(shí)我在談啥？...

miya 2019-07-30 18:03 評論0 收藏0
雪花算法（01）介紹

摘要：雪花算法生成的最終結(jié)果其實(shí)就是一個類型的長整型數(shù)字，這是一個大前提算法所有的內(nèi)容都是針對這個數(shù)字進(jìn)行運(yùn)算的。根據(jù)上面的理論可以開始學(xué)習(xí)雪花算法。針對每個公司，隨著服務(wù)化演進(jìn)，單個服務(wù)越來越多，數(shù)據(jù)庫分的越來越細(xì)，有的時(shí)候一個業(yè)務(wù)需要分成好幾個庫，這時(shí)候自增主鍵或者序列之類的主鍵id生成方式已經(jīng)不再滿足需求，分布式系統(tǒng)中需要的是一個全局唯一的id生成規(guī)則。既然號稱在全局分布式系統(tǒng)中唯一...

or0fun 2019-08-19 10:29 評論0 收藏0
十道簡單算法題二【Java實(shí)現(xiàn)】

摘要：前言清明不小心就拖了兩天沒更了這是十道算法題的第二篇了上一篇回顧十道簡單算法題最近在回顧以前使用寫過的數(shù)據(jù)結(jié)構(gòu)和算法的東西，發(fā)現(xiàn)自己的算法和數(shù)據(jù)結(jié)構(gòu)是真的薄弱，現(xiàn)在用改寫一下，重溫一下。前言清明不小心就拖了兩天沒更了～～這是十道算法題的第二篇了～上一篇回顧：十道簡單算法題最近在回顧以前使用C寫過的數(shù)據(jù)結(jié)構(gòu)和算法的東西，發(fā)現(xiàn)自己的算法和數(shù)據(jù)結(jié)構(gòu)是真的薄弱，現(xiàn)在用Java改寫一下，...

Pluser 2019-08-15 15:19 評論0 收藏0