在 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 次浏览

开启你的 职业生涯

通过完成课程获得认证

开始学习
广告