在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