資料結構
網路
關係資料庫管理系統 (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 次瀏覽
廣告