C++のソートされた配列に欠落している要素

一意の番号のソートされた配列Aがあるとすると、配列の左端の番号から始まるK番目の欠落している番号を見つける必要があります。したがって、配列が[4,7,9,10]のようで、k =1の場合、要素は5になります。

これを解決するには、次の手順に従います-

• n：=配列のサイズ、low：=0およびhigh：=n – 1

  に設定

• nums [n --1] – nums [0] + 1 – n

  • return nums [n-1] +（k –（nums [n-1] – nums [0] + 1 – n））

• 低<高– 1

  • 中：=低+（高-低）/ 2

  • 現在：=中–低+ 1

  • 不在：=nums [mid] – nums [low] + 1 –存在

  • 存在しない場合>=kの場合はhigh：=mid、それ以外の場合は存在しない場合はkを減少させます。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