Thiếu phần tử trong mảng đã sắp xếp trong C ++

Giả sử chúng ta có một mảng A đã được sắp xếp gồm các số duy nhất, chúng ta phải tìm số còn thiếu thứ K bắt đầu từ số tận cùng bên trái của mảng. Vì vậy, nếu mảng giống như [4,7,9,10] và k =1, thì phần tử sẽ là 5.

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

• n:=kích thước của mảng, đặt thấp:=0 và cao:=n - 1

• nếu nums [n - 1] - nums [0] + 1 - n

  • trả về nums [n - 1] + (k - (nums [n - 1] - nums [0] + 1 - n))

• trong khi thấp

  • giữa:=low + (cao - thấp) / 2

  • hiện tại:=mid - low + 1

  • vắng mặt:=nums [mid] - nums [low] + 1 - có mặt

  • nếu vắng mặt> =k thì cao:=giữa, ngược lại giảm k bằng cách vắng mặt, thấp:=giữa

• trả về số [thấp] + k

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

Ví dụ

#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));
}

Đầu vào

[4,7,9,10]
1

Đầu ra

5