We love coding - #4

Hi. I'm coding dog.

Let's solve today's coding interview problem.

Q: 給定一個整數陣列，請在線性時間和常數空間中找到第一個遺失的正整數。換句話說，找到陣列中不存在的最小正整數。陣列也可以包含重複項和負數。

A: 為了找到給定陣列中不存在的最小正整數，我們可以使用一個修改版的計數排序演算法，步驟如下：

1. 首先，我們遍歷整個陣列，忽略所有負數和零，因為它們不能是答案。
2. 對於所有剩下的正整數，我們在一個單獨的布爾陣列中標記它們的存在，稱為 present[]。具體來說，如果 A[i] 是一個正整數且存在於陣列中，則我們將 present[A[i]] 設為 true。
3. 最後，我們從索引 1 開始遍歷 present[] 陣列，直到找到第一個索引 i，使得 present[i] 為 false。這就是陣列中缺失的最小正整數。

以下是該演算法的 Python 代碼：

def find_first_missing_positive_integer(A):
    n = len(A)
    present = [False] * (n+1) # 創建布爾陣列來標記正整數的存在
    
    # 標記正整數的存在
    for i in range(n):
        if A[i] > 0 and A[i] <= n:
            present[A[i]] = True
    
    # 找到第一個遺失的正整數
    for i in range(1, n+1):
        if not present[i]:
            return i
    
    # 如果所有正整數都存在，則返回下一個整數
    return n+1

上述演算法的時間複雜度為 O(n)，空間複雜度為 O(n)（用於布爾陣列 present[]）。然而，由於輸入陣列是一個整數陣列，我們可以將空間複雜度優化為 O(1)，方法是使用輸入陣列本身作為布爾陣列。我們可以通過取負來標記正整數的存在。具體來說，如果 A[i] 是一個正整數，則我們將索引 A[i]-1 的值取負（因為陣列索引從 0 開始，而正整數從 1 開始）。以下是優化後的 Python 代碼：

def find_first_missing_positive_integer(A):
    n = len(A)
    
    # mark positive integers
    for i in range(n):
        if A[i] > 0 and A[i] <= n:
            j = A[i] - 1
            if A[j] > 0:
                A[j] *= -1
    
    # find first missing positive integer
    for i in range(n):
        if A[i] > 0:
            return i+1
    
    # if all positive integers are present, return next integer
    return n+1