在 Python 中查詢包含 1 到 N 元素的陣列中四個缺失的數字

假設我們有一個包含不同數字的陣列，每個數字都在 [1, N] 範圍內，陣列大小為 (N-4)，並且沒有單個元素重複。因此，我們可以理解陣列中缺少四個數字（從 1 到 N）。我們必須以排序方式找到這 4 個缺失的數字。

因此，如果輸入類似於 A =[2, 8, 4, 13, 6, 11, 9, 5, 10]，則輸出將為 [1, 3, 7, 12]

為了解決這個問題，我們將遵循以下步驟 -

  • temp_arr := 一個大小為 4 且所有元素都為 0 的陣列

  • 對於 i 從 0 到 A 的大小，執行以下操作

    • temp := |A[i]|

    • 如果 temp <= A 的大小，則

      • A[temp - 1] := A[temp - 1] *(-1)

    • 否則，當 temp > A 的大小時，

      • 如果 temp 對 A 的大小取模不為零，則

        • temp_arr[temp 對 A 的大小取模 - 1] := -1

      • 否則，

        • temp_arr[(temp 對 A 的大小取模) + A 的大小 - 1] := -1

  • 對於 i 從 0 到 A 的大小，執行以下操作

    • 如果 A[i] > 0，則

      • 顯示 i + 1

  • 對於 i 從 0 到 temp_arr 的大小，執行以下操作

    • 如果 temp_arr[i] >= 0，則

      • 顯示 A 的大小 + i + 1

示例

讓我們看看以下實現以獲得更好的理解 -

 線上演示

def find_missing_nums(A) :
   temp_arr = [0]*4
   for i in range(0,len(A)) :
      temp = abs(A[i])
      if (temp <= len(A)) :
         A[temp - 1] = A[temp - 1] * (-1)
      elif (temp > len(A)) :
         if (temp % len(A)) :
            temp_arr[temp % len(A) - 1] = -1
         else :
            temp_arr[(temp % len(A)) +len(A) - 1] = -1
   for i in range(0, len(A) ) :
      if (A[i] > 0) :
         print((i + 1) , end=" ")
   for i in range(0, len(temp_arr)) :
      if (temp_arr[i] >= 0) :
         print((len(A) + i + 1) , end=" ")
A = [2, 8, 4, 13, 6, 11, 9, 5, 10]
find_missing_nums(A)

輸入

[2, 8, 4, 13, 6, 11, 9, 5, 10]

輸出

1 3 7 12

更新於: 2020-08-25

167 次瀏覽

開啟你的 職業生涯

透過完成課程獲得認證

開始學習
廣告