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

C++ में सॉर्टेड एरे में मिसिंग एलिमेंट


मान लीजिए हमारे पास अद्वितीय संख्याओं का एक सॉर्टेड एरे A है, हमें एरे के बाएं सबसे नंबर से शुरू होने वाले K-वें मिसिंग नंबर को ढूंढना है। इसलिए अगर एरे [4,7,9,10] है, और k = 1, तो एलिमेंट 5 होगा।

इसे हल करने के लिए, हम इन चरणों का पालन करेंगे:

  • n := एरे का आकार, low := 0 और high := n - 1 सेट करें

  • यदि nums[n - 1] - nums[0] + 1 - n < k, तो

    • nums[n - 1] + (k - (nums[n - 1] - nums[0] + 1 - n)) लौटाएं

  • जब तक low < high - 1:

    • mid := low + (high - low)/2

    • present := mid - low + 1

    • absent := nums[mid] - nums[low] + 1 - present

    • यदि absent >= k तो high := mid, अन्यथा k को absent से घटाएं, low := mid

  • nums[low] + k लौटाएं

बेहतर समझ के लिए निम्नलिखित कार्यान्वयन देखें:

उदाहरण

#include <bits/stdc++.h> using namespace std; class Solution {    public:    int missingElement(vector<int>& nums, int k) {       int n = nums.size();       int low = 0;       int high = n - 1;       if(nums[n - 1] - nums[0] + 1 - n < k) return nums[n - 1] + (k       - ( nums[n - 1] - nums[0] + 1 - n)) ;       while(low < high - 1){          int mid = low + (high - low) / 2;          int present = mid - low + 1;          int absent = nums[mid] - nums[low] + 1 - present;          if(absent >= k){             high = mid;           }else{             k -= absent;             low = mid;           }       }       return nums[low] + k;    } }; main(){    vector<int> v = {4,7,9,10};    Solution ob;    cout << (ob.missingElement(v, 1)); }

इनपुट

[4,7,9,10] 1

आउटपुट

5

  1. - C++ में सॉर्टेड एरे में निरपेक्ष विशिष्ट गिनती

    एक एरे समान डेटा प्रकार के तत्वों का एक संग्रह है। एक सॉर्टेड एरे एक एरे है जिसमें तत्व आरोही या अवरोही क्रम के अनुक्रम में संग्रहीत होते हैं। विशिष्ट गिनती उन तत्वों की संख्या है जो समान नहीं हैं। निरपेक्ष विशिष्ट गिनती तत्वों के निरपेक्ष मान की विशिष्ट गिनती है यानी चिह्न के बिना मान (अनसाइन्ड मा

  1. - C++ प्रोग्राम: सॉर्टेड ऐरे कार्यान्वयन (सिलेक्शन सॉर्ट)

    सॉर्टेड ऐरे ऐरे जिसमें तत्व क्रमबद्ध क्रम में हों (संख्यात्मक, वर्णानुक्रमिक, आदि)। कई सॉर्टिंग एल्गोरिदम: बबल सॉर्ट, इन्सर्शन सॉर्ट, सिलेक्शन सॉर्ट, मर्ज सॉर्ट, क्विक सॉर्ट, हीप सॉर्ट। सिलेक्शन सॉर्ट अनसॉर्टेड भाग में सबसे छोटा तत्व ढूंढकर उसे शुरुआत से स्वैप करता है। O(n²) समय जटिलता। C++ प्रोग

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

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