สมมติว่าเรามีอาร์เรย์ที่จัดเรียง A ของตัวเลขที่ไม่ซ้ำกัน เราต้องหาตัวเลขที่หายไปที่ K โดยเริ่มจากหมายเลขซ้ายสุดของอาร์เรย์ ดังนั้นหากอาร์เรย์เป็นแบบ [4,7,9,10] และ k =1 อิลิเมนต์จะเป็น 5
เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -
-
n :=ขนาดของอาร์เรย์ ตั้งค่าต่ำ :=0 และสูง :=n – 1
-
ถ้า nums[n - 1] – nums[0] + 1 – n
-
คืนค่า nums[n - 1] + (k – (nums[n - 1] – nums[0] + 1 – n))
-
-
ในขณะที่ต่ำ <สูง – 1
-
กลาง :=ต่ำ + (สูง - ต่ำ)/2
-
ปัจจุบัน :=กลาง – ต่ำ + 1
-
ไม่อยู่ :=nums[mid] – nums[low] + 1 – ปัจจุบัน
-
ถ้าขาด>=k แสดงว่าสูง :=กลาง ไม่เช่นนั้นให้ลด k โดยขาด ต่ำ :=กลาง
-
-
คืนค่า nums[ต่ำ] + 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
