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


概念

对于给定的唯一整数数组,其中每个整数都在范围 [1, N] 内,数组大小为 (N-4),并且没有单个元素重复。因此,数组中缺少四个数字(从 1 到 N)。确定这四个缺失的数字(按升序排列)。

输入

arr[] = {3, 6, 7, 4, 10}

输出

1 2 5 8 9

输入

arr[] = { 2, 8, 4, 13, 6, 11, 9, 5, 10 }

输出

1 3 7 12

方法

一个简单的 O(N) 解决方案是实现一个大小为 N 的辅助数组来指示或标记已访问的元素。访问输入数组并指示或标记辅助数组中的元素。最后打印所有未指示或标记的索引。

现在的问题是如何使用 O(1) 的辅助空间来解决?

首先,我们初始化一个名为 helper 长度为 4 的数组,以补偿 4 个缺失的数字,并用零填充它们。然后,我们从 i=0 迭代到 i < 输入数组的长度,并获取第 i 个元素的绝对值,并将其存储在一个名为 temp 的变量中。此时,我们将验证:

  • 如果元素的绝对值小于输入数组的长度,我们将把 array[temp] 元素乘以 -1(为了指示或标记已访问的元素)。

  • 如果元素的绝对值大于输入数组的长度,我们将把 helper[temp%array.length] 元素的值设为 -1(为了指示或标记已访问的元素)。

现在我们遍历输入数组,那些值仍然大于零的索引表示这些元素在输入数组中没有出现。因此,我们打印值为大于零的索引的 (index+1) 值。

现在我们将遍历 helper 数组,那些值仍然大于零的索引表示这些元素在输入数组中没有出现。因此,我们打印值为大于零的索引的 (index+array.length+1) 值。

示例

 在线演示

// CPP program to find missing 4 elements
// in an array of size N where elements are
// in range from 1 to N+4.
#include <bits/stdc++.h>
using namespace std;
// Used to find missing 4 numbers in O(N) time
// and O(1) auxiliary space.
void missing4(int arr1[], int n1){
   // Used to keep track of 4 possible numbers
   // greater than length of input array
   // In case of Java, helper is automatically
   // initialized as 0.
   int helper[4];
   // Visit the input array and mark
   // visited elements either by marking
   // them as negative in arr[] or in
   // helper[].
   for (int i = 0; i < n1; i++) {
      int temp1 = abs(arr1[i]);
      // It has been seen that if element is smaller than or
      // equal to length, mark its
      // presence in arr1[]
      if (temp1 <= n1)
         arr1[temp1 - 1] *= (-1);
      // Indicate or mark presence in helper[]
      else if (temp1 > n1) {
         if (temp1 % n1 != 0)
            helper[temp1 % n1 - 1] = -1;
         else
            helper[(temp1 % n1) + n1 - 1] = -1;
      }
   }
   // Used to print all those elements whose presence
   // is not marked.
   for (int i = 0; i < n1; i++)
      if (arr1[i] > 0)
         cout << (i + 1) << " ";
   for (int i = 0; i < 4; i++)
      if (helper[i] >= 0)
         cout << (n1 + i + 1) << " ";
      return;
}
// Driver code
int main(){
   int arr1[] = { 2, 8, 4, 13, 6, 11, 9, 5, 10 };
   int n1 = sizeof(arr1) / sizeof(arr1[0]);
   missing4(arr1, n1);
   return 0;
}

输出

1 3 7 12

更新于:2020年7月24日

114 次浏览

启动您的职业生涯

完成课程获得认证

开始学习
广告