41 缺失的第一個(gè)正數(shù)
給你一個(gè)未排序的整數(shù)數(shù)組 nums ，請(qǐng)你找出其中沒有出現(xiàn)的最小的正整數(shù)。
請(qǐng)你實(shí)現(xiàn)時(shí)間復(fù)雜度為 O(n) 并且只使用常數(shù)級(jí)別額外空間的解決方案。
示例 1：
輸入：nums = [1,2,0]
輸出：3
示例 2：
輸入：nums = [3,4,-1,1]
輸出：2
示例 3：
輸入：nums = [7,8,9,11,12]
輸出：1
方法一：暴力解題，復(fù)雜度超出范圍

from typing import List
def firstMissingPositive(nums: List[int]) -> int:
    for i in nums:
        if i<0:
            nums.remove(i)
    nums.sort()
    b = []
    for i in range(0,max(nums)+2):
        if i not in nums:
            b.append(i)
    b.sort()
    if b[0]==0:
        b.remove(b[0])
    if b==[]:
        return max(nums)+1
    else:
        return min(b)

nums=[3,4,-1,1,9,-5]
a=firstMissingPositive(nums)
print(a)
#以上方法判定為超出內(nèi)存限制！?。?！

方法二：
沒有排序或者暴力循環(huán)
總體思路：
1對(duì)于一個(gè)長度為 N 的數(shù)組，其中沒有出現(xiàn)的最小正整數(shù)只能在 [1,N+1]中。這是因?yàn)槿绻?[1,N] 都出現(xiàn)了，那么答案是 N+1，否則答案是 [1,N] 中沒有出現(xiàn)的最小正整數(shù)
2我們對(duì)數(shù)組進(jìn)行遍歷，對(duì)于遍歷到的數(shù) x，如果它在 [1,N]的范圍內(nèi)，那么就將數(shù)組中的第 x?1個(gè)位置（注意：數(shù)組下標(biāo)從 0開始）打上「標(biāo)記」。在遍歷結(jié)束之后，如果所有的位置都被打上了標(biāo)記，那么答案是 N+1，否則答案是最小的沒有打上標(biāo)記的位置加 1
3由于我們只在意 [1,N] 中的數(shù)，因此我們可以先對(duì)數(shù)組進(jìn)行遍歷，把不在 [1,N] 范圍內(nèi)的數(shù)修改成任意一個(gè)大于 N 的數(shù)（例如 N+1）。這樣一來，數(shù)組中的所有數(shù)就都是正數(shù)了，因此我們就可以將「標(biāo)記」表示為「負(fù)號(hào)」

from typing import List
def firstMissingPositive(nums: List[int]) -> int:
    n = len(nums)
    for i in range(n):
        if nums[i] <= 0:
            nums[i] = n + 1
    print(nums)
    #凡是0和負(fù)數(shù)都變?yōu)閚+1#[3, 4, 7, 1, 9, 7]，因?yàn)檫@里面7和9數(shù)字大于n=6，
    #后面都會(huì)忽略處理它們，因?yàn)槿笔У牡?個(gè)正整數(shù)不可能是它們.
    #除非[1,n]都出現(xiàn)了，那么缺失的第1個(gè)正整數(shù)會(huì)是n+1見下面的return
    for i in range(n):
        num = abs(nums[i])
        #依次處理nums中的值,注意由于下面的處理nums中的值一直在變化
        # #但是nums中各個(gè)值的絕對(duì)值是不變的
        print("num:",num)
        #核心思路：不管nums如何變化這里num依次取到的值依然是3, 4, 7, 1, 9, 7
        # num為3時(shí)把第2個(gè)位置的數(shù)字改為第2個(gè)位置中的數(shù)字的負(fù)數(shù)即把7變?yōu)?7
        #即后面處理的依然可以取到7這個(gè)數(shù)字，
        #又在[1,n]中3處在第3個(gè)位置，也就是python列表的第2個(gè)位置，這里把第2個(gè)位置7標(biāo)為負(fù)數(shù)
        #意味著第2個(gè)位置標(biāo)記為負(fù)數(shù)了，則第2個(gè)位置上數(shù)即2+1=3，即3不可能是缺失的第1個(gè)正整數(shù)
        if num <= n:
            nums[num - 1] = -abs(nums[num - 1])
            print("nums:",nums)#
    for i in range(n):
        if nums[i] > 0:
            return i + 1
    return n + 1

nums=[3,4,-1,1,9,-5]
a=firstMissingPositive(nums)
print(a)#a的范圍肯定在[1,n+1]之間

方法三、文章來源地址http://www.zghlxwxcb.cn/news/detail-673136.html

到了這里，關(guān)于力扣數(shù)組類題目--41缺失的第一個(gè)正數(shù)的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！