C++에서 정렬된 배열의 누락된 요소

고유한 숫자의 정렬된 배열 A가 있다고 가정하고 배열의 가장 왼쪽 숫자부터 시작하여 K번째 누락된 숫자를 찾아야 합니다. 따라서 배열이 [4,7,9,10]이고 k =1이면 요소는 5가 됩니다.

이 문제를 해결하기 위해 다음 단계를 따릅니다. −

• n :=배열의 크기, low :=0, high :=n – 1

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

  • 반환 숫자[n - 1] + (k – (숫자[n - 1] – 숫자[0] + 1 – n))

• 낮음 <높음 – 1

  동안

  • 중간 :=낮음 + (높음 - 낮음)/2

  • 현재 :=중간 – 낮음 + 1

  • 부재 :=nums[mid] – nums[low] + 1 – 존재함

  • 없는 경우>=k 다음 높음 :=중간, 그렇지 않으면 k를 부재로 감소, 낮음 :=중간

• 반환 숫자[낮음] + 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