Computer >> कंप्यूटर ट्यूटोरियल >  >> प्रोग्रामिंग >> C++

C++ में क्रमबद्ध सरणी में लगातार संख्याओं में लापता तत्व ढूंढना


अवधारणा

दिए गए सरणी array[] के संबंध में जिसमें n विशिष्ट पूर्णांक हैं, तत्व आरोही क्रम में एक लापता तत्व के साथ क्रमिक रूप से रखे गए हैं। हमारा कार्य लापता तत्व निर्धारित करना है।

इनपुट

array[] = {1, 2, 3, 4, 5, 6, 7, 9}

आउटपुट

8

इनपुट

array[] = {-4, -2, -1, 0, 1, 2}

आउटपुट

-3

इनपुट

array[] = {1, 2, 3, 4}

आउटपुट

-1

कोई तत्व लापता नहीं है।

विधि

सिद्धांत

  • असंगति देखें: इस सिद्धांत के अनुसार, किसी भी तत्व और उसके सूचकांक के बीच का अंतर हर तत्व के लिए array[0] होना चाहिए।

उदाहरण,

A[] = {1, 2, 3, 4, 5} -> सुसंगत

B[] = {201, 202, 203, 204} -> सुसंगत

C[] = {1, 2, 3, 5, 6} -> असंगत क्योंकि C[3] - 3 != C[0] यानी 5 - 3 != 1

  • असंगति निर्धारित करने से प्रत्येक बार सरणी के केवल आधे हिस्से को O(logN) में स्कैन करने में मदद मिलती है।

एल्गोरिदम

  • मध्य तत्व ढूंढें और जांचें कि क्या यह सुसंगत है।

  • यदि मध्य तत्व सुसंगत है, तो जांचें कि मध्य तत्व और उसके अगले तत्व के बीच का अंतर 1 से अधिक है यानी जांचें कि array[mid + 1] - array[mid] > 1

    • यदि हां, तो array[mid] + 1 लापता तत्व है।

    • अन्यथा, हमें मध्य तत्व से सरणी के दाएं आधे हिस्से को स्कैन करना होगा और चरण-1 पर जाना होगा।

  • यदि मध्य तत्व असंगत है, तो जांचें कि मध्य तत्व और उसके पिछले तत्व के बीच का अंतर 1 से अधिक है यानी जांचें कि array[mid] - array[mid - 1] > 1

    • यदि हां, तो array[mid] - 1 लापता तत्व है।

    • अन्यथा, हमें मध्य तत्व से सरणी के बाएं आधे हिस्से को स्कैन करना होगा और चरण-1 पर जाना होगा।

उदाहरण

// दृष्टिकोण का CPP कार्यान्वयन #include<bits/stdc++.h> using namespace std; // लापता तत्व लौटाने के लिए फ़ंक्शन दिखाता है int findMissing(int array[], int n1){    int low = 0, high = n1 - 1;    int mid1;    while (high > low){       mid1 = low + (high - low) / 2;       // जांचें कि क्या मध्य तत्व सुसंगत है       if (array[mid1] - mid1 == array[0]){          // मध्य तत्वों तक कोई असंगति नहीं          // जब लापता तत्व ठीक मध्य तत्व के बाद है          if (array[mid1 + 1] - array[mid1] > 1)             return array[mid1] + 1;          else{             // दाएं जाएं             low = mid1 + 1;          }       }       else{          // यहां असंगति मिली          // जब लापता तत्व ठीक मध्य तत्व के पहले है          if (array[mid1] - array[mid1 - 1] > 1)             return array[mid1] - 1;          else{             // बाएं जाएं             high = mid1 - 1;          }       }    }    // यहां, कोई लापता तत्व नहीं मिला    return -1; } // ड्राइवर कोड int main(){    int array[] = { -9, -8, -6, -5, -4, -3, -2, -1, 0 };    int n1 = sizeof(array)/sizeof(array[0]);    cout <<"लापता तत्व:" <<(findMissing(array, n1)); }

आउटपुट

लापता तत्व:-7

  1. - C++ प्रोग्राम: अनसॉर्टेड सरणी में k निकटतम संख्याएं ज्ञात करना

    मान लें हमारे पास कुछ तत्वों के साथ एक सरणी A है। सरणी अनसॉर्टेड है। हमारे पास दो अन्य मान X और k हैं। हमारा कार्य सरणी A से X की k निकटतम तत्वों की संख्या ज्ञात करना है। यदि तत्व X सरणी में मौजूद है, तो यह आउटपुट में नहीं दिखाया जाएगा। यदि A = [48, 50, 55, 30, 39, 35, 42, 45, 12, 16, 53, 22, 56] और

  1. - C++ में सरणी का सबसे बड़ा एलिमेंट खोजने का प्रोग्राम

    एक सरणी में कई एलिमेंट्स होते हैं और सरणी में सबसे बड़ा एलिमेंट वह होता है जो अन्य एलिमेंट्स से बड़ा होता है। उदाहरण के लिए। 5 1 7 2 4 उपरोक्त सरणी में, 7 सबसे बड़ा एलिमेंट है और यह इंडेक्स 2 पर है। सरणी का सबसे बड़ा एलिमेंट खोजने का एक प्रोग्राम निम्नलिखित है। उदाहरण #include <iostream>

  1. - Python में लगातार संख्याओं की क्रमबद्ध सरणी में लापता तत्व ढूंढना

    मान लीजिए हमारे पास n अद्वितीय संख्याओं की एक सरणी A है, ये n तत्व सरणी में आरोही क्रम में मौजूद हैं, लेकिन एक लापता तत्व है। हमें लापता तत्व ढूंढना है। तो, यदि इनपुट A = [1, 2, 3, 4, 5, 6, 7, 9] की तरह है, तो आउटपुट 8 होगा। इसे हल करने के लिए, हम इन चरणों का पालन करेंगे - n := A का आकार left := 0