We love coding - #4

2023/03/08閱讀時間約 3 分鐘
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
CodingDog
CodingDog
留言0
查看全部
發表第一個留言支持創作者!