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

Z时代
2024-01-10
分类：综合

概念

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

输入值

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)辅助空间求解？

首先，我们初始化一个长度为4的名为辅助程序的数组，以补偿4个缺失的数字并将其填充为零。之后，我们从i = 0迭代到给定数组的i <length_of_array，并接受第i个元素的绝对值，并将其存储在名为temp的变量中。这一次，我们将验证-

已经看到，如果元素的绝对值小于输入数组的长度，则我们将array [temp]元素乘以-1（以指示或标记被访问的元素）。
已经看到，如果元素的绝对值大于输入数组的长度，则我们将helper [temp％array.length]元素的值设为-1（以指示或标记访问的元素）。

现在，我们遍历输入数组和那些其值仍大于零的索引，然后在输入数组中未遇到那些元素。结果，我们打印出元素大于零的索引的（index + 1）值。

现在，我们将遍历helper数组和那些其值仍大于零的索引，然后在输入数组中未遇到那些元素。结果，我们打印出元素大于零的索引的（index + array.length + 1）值。

示例

// CPP program to find missing 4 elements
//在大小为N的数组中，元素为
//范围从1到N + 4。
#include <bits/stdc++.h>
using namespace std;
//用于查找O(N)时间中缺少的4个数字
//和O(1)辅助空间。
void missing4(int arr1[], int n1){
   //用于跟踪4个可能的数字
   //大于输入数组的长度
   //如果是Java，helper会自动
   //初始化为0。-
   int helper[4];
   //访问输入数组并标记
   //访问元素
   //为负数
   //帮手[]。
   for (int i = 0; i < n1; i++) {
      int temp1 = abs(arr1[i]);
      //已经看到，如果element小于或
      //等于长度，标记其
      //存在于arr1 []
      if (temp1 <= n1)
         arr1[temp1 - 1] *= (-1);
      //指示或标记助手中的存在[]
      else if (temp1 > n1) {
         if (temp1 % n1 != 0)
            helper[temp1 % n1 - 1] = -1;
         else
            helper[(temp1 % n1) + n1 - 1] = -1;
      }
   }
   //用于打印所有存在的元素
   //没有标记。
   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;
}
//驱动程式码
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;
}