แนวคิด
สำหรับอาร์เรย์ของจำนวนเต็มเฉพาะที่กำหนด ซึ่งแต่ละจำนวนเต็มของอาร์เรย์ที่กำหนดจะอยู่ในช่วง [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) auxiliary space ยังไงดี
ตอนแรกเราเริ่มต้นอาร์เรย์ชื่อ helper ที่มีความยาว 4 เพื่อชดเชย 4 ตัวเลขที่ขาดหายไปและเติมด้วยศูนย์ หลังจากนั้นเราทำซ้ำจาก i=0 ถึง i
จะเห็นได้ว่าหากค่าสัมบูรณ์ขององค์ประกอบน้อยกว่าความยาวของอินพุตอาร์เรย์ เราจะคูณองค์ประกอบ array[temp] ด้วย -1 (เพื่อระบุหรือทำเครื่องหมายองค์ประกอบที่เข้าชม)
จะเห็นได้ว่าหากค่าสัมบูรณ์ขององค์ประกอบมากกว่าความยาวของอินพุตอาร์เรย์ เราจะใส่ค่าขององค์ประกอบ helper[temp%array.length] ด้วย -1 (เพื่อระบุหรือทำเครื่องหมายองค์ประกอบที่เข้าชม)
ตอนนี้เราวนซ้ำผ่านอาร์เรย์อินพุตและดัชนีที่มีค่ายังคงมากกว่าศูนย์ จากนั้นไม่พบองค์ประกอบเหล่านั้นในอาร์เรย์อินพุต ด้วยเหตุนี้ เราจึงพิมพ์ค่า (index+1) ของดัชนีที่มีองค์ประกอบมากกว่าศูนย์
ตอนนี้ เราจะวนซ้ำในอาร์เรย์ตัวช่วยและดัชนีที่มีค่ายังคงมากกว่าศูนย์ จากนั้นไม่พบองค์ประกอบเหล่านั้นในอาร์เรย์อินพุต ด้วยเหตุนี้ เราจึงพิมพ์ค่า (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
