在 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
广告