数据结构
网络
关系数据库管理系统 (RDBMS)
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化学
生物
数学
英语
经济学
心理学
社会研究
时尚研究
法律研究在 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
更新于：2020年7月24日
114 次浏览
广告