แนวคิด
สำหรับอาร์เรย์ของจำนวนเต็มเฉพาะที่กำหนด ซึ่งแต่ละจำนวนเต็มของอาร์เรย์ที่กำหนดจะอยู่ในช่วง [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