C++ এ সাজানো অ্যারেতে অনুপস্থিত উপাদান

ধরুন আমাদের কাছে অনন্য সংখ্যাগুলির একটি সাজানো অ্যারে রয়েছে, আমাদের অ্যারের বাম নম্বর থেকে শুরু করে K-তম অনুপস্থিত সংখ্যাটি খুঁজে বের করতে হবে। তাই অ্যারে যদি হয় [4,7,9,10], এবং k =1, তাহলে উপাদানটি হবে 5।

এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -

• n :=অ্যারের আকার, কম সেট করুন :=0 এবং উচ্চ :=n – 1

• যদি nums[n - 1] – nums[0] + 1 - n

  • রিটার্ন সংখ্যা [n - 1] + (k – (সংখ্যা [n - 1] – সংখ্যা[0] + 1 - n))

• যখন কম <উচ্চ – 1

  • মধ্য :=নিম্ন + (উচ্চ - নিম্ন)/2

  • বর্তমান :=মধ্য – নিম্ন + 1

  • অনুপস্থিত :=সংখ্যা[মধ্য] - সংখ্যা [নিম্ন] + 1 - বর্তমান

  • অনুপস্থিত থাকলে>=k তারপর উচ্চ :=মধ্য, অন্যথায় অনুপস্থিত দ্বারা k হ্রাস করুন, নিম্ন :=মধ্য

• রিটার্ন 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