Find K Closest Elements trong C++

Cho mảng đã sắp xếp, số nguyên k và x. Tìm k phần tử gần x nhất. Kết quả sắp xếp tăng dần. Nếu tie, ưu tiên phần tử nhỏ hơn.

Ví dụ: arr=[1,2,3,4,5], k=4, x=3 → [1,2,3,4].

Giải thuật (Binary Search)

• Khởi tạo low=0, high=n-k.
• Khi low < high:
  • mid = low + (high-low)/2.
  • Nếu x - arr[mid] > arr[mid+k] - x thì low = mid+1, ngược lại high = mid.
• Lấy k phần tử từ low đến low+k-1.

Ví dụ code

#include <bits/stdc++.h>
using namespace std;

class Solution {
public:
    vector<int> findClosestElements(vector<int>& arr, int k, int x) {
        vector<int> ans;
        int low = 0, 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;
    }
};

int main() {
    Solution ob;
    vector<int> v = {1,2,3,4,5};
    for (int x : ob.findClosestElements(v, 4, 3)) cout << x << " ";
    return 0;
}

Input

[1,2,3,4,5] 4 3

Output

1 2 3 4