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

概念

对于给定的唯一整数数组,其中给定数组的每个整数都在[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;
}

输出结果

1 3 7 12