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