在 Python 中查找包含 1 到 N 元素的数组中的四个缺失数字

pythonserver side programmingprogramming更新于 2025/10/10 7:40:17

假设我们有一个包含不同数字的数组,其中每个数字位于 [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 的数组

  • 对于范围从 0 到 A 的大小的 i,执行

    • temp := |A[i]|

    • 如果 temp <= A 的大小,则

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

    • 否则,当 temp > size of A 时,则

      • 如果 temp mod size of A 非零,则

        • temp_arr[temp mod size of A - 1] := -1

      • 否则,

        • temp_arr[(temp mod size of A) +size of A - 1] := -1

  • 对于 i 在 0 到 A 大小范围内的情况,执行

    • 如果 A[i] > 0,则

      • 显示 i + 1

  • 对于介于 0 到 temp_arr 大小之间的 i,执行

    • 如果 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

相关文章


有用资源