अवधारणा
एक दी गई अद्वितीय पूर्णांकों की सरणी के संबंध में जहां दी गई सरणी का प्रत्येक पूर्णांक रेंज [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) सहायक स्थान के साथ कैसे हल करें?
सबसे पहले हम हेल्पर नामक एक सरणी को लंबाई 4 के साथ इनिशियलाइज़ करते हैं ताकि 4 गायब संख्याओं की भरपाई की जा सके और उन्हें शून्य से भरें। उसके बाद हम i=0 से i < दी गई सरणी की लंबाई तक पुनरावृति करते हैं और i-वें तत्व का निरपेक्ष मान लेकर एक वेरिएबल टेम्प में संग्रहीत करते हैं। इस समय, हम सत्यापित करेंगे −
<उल क्लास="सूची"><ली>यह देखा गया है कि यदि तत्व का निरपेक्ष मान इनपुट सरणी की लंबाई से छोटा है तो हम सरणी[टेम्प] तत्व को -1 से गुणा करेंगे (देखे गए तत्व को इंगित या चिह्नित करने के क्रम में)।
ली><ली>यह देखा गया है कि यदि तत्व का निरपेक्ष मान इनपुट सरणी की लंबाई से बड़ा है तो हम हेल्पर[टेम्प%सरणी.लंबाई] तत्व के मान को -1 से रखेंगे (देखे गए तत्व को इंगित या चिह्नित करने के क्रम में)।
ली>उल>अब हम इनपुट सरणी पर पुनरावृति करते हैं और वे इंडेक्स जिनका मान अभी भी शून्य से बड़ा है तो वे तत्व इनपुट सरणी में नहीं मिले। इसके परिणामस्वरूप हम (इंडेक्स+1) मान प्रिंट करते हैं जिस इंडेक्स का तत्व शून्य से बड़ा है।
अब हम हेल्पर सरणी पर पुनरावृति करेंगे और वे इंडेक्स जिनका मान अभी भी शून्य से बड़ा है तो वे तत्व इनपुट सरणी में नहीं मिले। इसके परिणामस्वरूप हम (इंडेक्स+सरणी.लंबाई+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; // O(N) समय और O(1) सहायक स्थान में गायब 4 संख्याएं खोजने के लिए उपयोग किया जाता है। void missing4(int arr1[], int n1){ // 4 संभावित संख्याओं का ट्रैक रखने के लिए उपयोग किया जाता है // जो इनपुट सरणी की लंबाई से बड़ी हैं // जावा के मामले में, हेल्पर स्वचालित रूप से // 0 के रूप में इनिशियलाइज़ होता है। int helper[4]; // इनपुट सरणी पर जाएं और // देखे गए तत्वों को या तो arr[] में ऋणात्मक के रूप में चिह्नित करके // या हेल्पर[] में चिह्नित करें। for (int i = 0; i < n1; i++) { int temp1 = abs(arr1[i]); // यह देखा गया है कि यदि तत्व छोटा है या // लंबाई के बराबर है, तो इसकी // उपस्थिति को arr1[] में चिह्नित करें if (temp1 <= n1) arr1[temp1 - 1] *= (-1); // हेल्पर[] में उपस्थिति इंगित या चिह्नित करें else if (temp1 > n1) { if (temp1 % n1 != 0) helper[temp1 % n1 - 1] = -1; else helper[(temp1 % n1) + n1 - 1] = -1; } } // उन सभी तत्वों को प्रिंट करने के लिए उपयोग किया जाता है जिनकी उपस्थिति // चिह्नित नहीं है। 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; } // ड्राइवर कोड 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