สมมติว่าเรามีอาร์เรย์ที่จัดเรียงแล้ว โดยจะมีจำนวนเต็มสองตัว k และ x ด้วย เราต้องหาองค์ประกอบ k ที่ใกล้เคียงที่สุดกับ x ในอาร์เรย์นั้น ผลลัพธ์ควรเรียงลำดับเพิ่มขึ้น หากเสมอกัน ควรใช้องค์ประกอบที่เล็กกว่าเสมอ ดังนั้นหากอินพุตเป็น [1,2,3,4,5] และ k =4, x =3 เอาต์พุตจะเป็น [1,2,3,4]
เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -
- สร้างอาร์เรย์ที่เรียกว่า ans
- ตั้งค่าต่ำ :=0, สูง :=ขนาดของอาร์เรย์ – k
- ในขณะที่ต่ำ <สูง
- กลาง :=ต่ำ + (สูง - ต่ำ) /2
- ถ้า x – arr[mid]> arr[mid + k] – x แล้วต่ำ :=mid + 1 มิฉะนั้น high :=mid
- สำหรับ i ในช่วงต่ำไปต่ำ + k
- แทรก arr[i] ลงใน ans array
- คืนสินค้า
ตัวอย่าง(C++)
ให้เราดูการใช้งานต่อไปนี้เพื่อทำความเข้าใจ −
#include <bits/stdc++.h>
using namespace std;
void print_vector(vector<auto> v){
cout << "[";
for(int i = 0; i<v.size(); i++){
cout << v[i] << ", ";
}
cout << "]"<<endl;
}
class Solution {
public:
vector<int> findClosestElements(vector<int>& arr, int k, int x) {
vector <int> ans;
int low = 0;
int high = arr.size() - k;
while(low < high){
int mid = low + (high - low)/2;
if(x - arr[mid] > arr[mid + k] - x){
low = mid + 1;
}
else high = mid;
}
for(int i = low ; i < low + k ; i++)ans.push_back(arr[i]);
return ans;
}
};
main(){
Solution ob;
vector<int> v = {1,2,3,4,5};
print_vector(ob.findClosestElements(v, 4, 3));
} อินพุต
[1,2,3,4,5] 4 3
ผลลัพธ์
[1,2,3,4]
