मान लीजिए हमारे पास अद्वितीय संख्याओं का एक सॉर्टेड एरे 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