Giả sử ta có mảng đã sắp xếp A các số duy nhất, ta phải tìm số thứ K bị thiếu tính từ số ngoài cùng bên trái của mảng. Ví dụ, mảng [4,7,9,10], k = 1, phần tử sẽ là 5.
Để giải quyết, ta thực hiện các bước sau:
n := kích thước mảng, low := 0, high := n - 1.
Nếu nums[n - 1] - nums[0] + 1 - n < k, thì:
Trả về nums[n - 1] + (k - (nums[n - 1] - nums[0] + 1 - n)).
Khi low < high - 1:
mid := low + (high - low)/2.
present := mid - low + 1.
absent := nums[mid] - nums[low] + 1 - present.
Nếu absent >= k thì high := mid, ngược lại giảm k đi absent, low := mid.
Trả về nums[low] + k.
Xem triển khai dưới đây để hiểu rõ hơn:
Ví dụ minh họa
#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
Kết quả
5