Find K Closest Elements ใน C++

ตัวอย่าง: arr = [1,2,3,4,5], k = 4, x = 3

ระยะห่าง: 1→2, 2→1, 3→0, 4→1, 5→2

4 ตัวที่ใกล้ที่สุด: 1, 2, 3, 4 (5 ระยะห่าง 2 เท่ากับ 1 แต่ 1 น้อยกว่า 5 จึงเลือก 1)

ผลลัพธ์: [1,2,3,4]

อัลกอริทึม: Binary Search บนตำแหน่งเริ่มต้นของหน้าต่าง

เนื่องจากอาร์เรย์เรียงลำดับแล้ว k องค์ประกอบที่ใกล้ที่สุดจะต้องเป็น ซับอาร์เรย์ติดต่อกัน (contiguous subarray) ขนาด k ให้หา ตำแหน่งเริ่มต้น (left) ของหน้าต่างนี้

1. กำหนด low = 0, high = n - k (ตำแหน่งเริ่มต้นสูงสุดคือ n-k)
2. Binary search while low < high:
   • mid = low + (high - low) / 2
   • เปรียบเทียบระยะห่าง: x - arr[mid] vs arr[mid + k] - x
   • หาก x - arr[mid] > arr[mid + k] - x → ขอบซ้ายอยู่ไกลกว่า ขยายขวา: low = mid + 1
   • มิฉะนั้น → หดซ้าย: high = mid
3. ตำแหน่งเริ่มต้นคือ low ส่งคืน arr[low ... low+k-1]

เหตุผล: หากขอบซ้าย (arr[mid]) ห่างจาก x มากกว่าขอบขวา (arr[mid+k]) แสดงว่าควรเลื่อนหน้าต่างไปขวา

ตัวอย่างโค้ด C++

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

void print_vector(vector<int> v) {
    cout << "[";
    for (int i = 0; i < v.size(); i++) {
        cout << v[i];
        if (i + 1 < v.size()) cout << ", ";
    }
    cout << "]" << endl;
}

class Solution {
public:
    vector<int> findClosestElements(vector<int>& arr, int k, int x) {
        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;
            }
        }
        
        vector<int> ans;
        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};
    print_vector(ob.findClosestElements(v, 4, 3));
    return 0;
}

Input

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

Output

[1, 2, 3, 4]

ความซับซ้อน (Complexity)

• เวลา: O(log(n-k) + k) ≈ O(log n + k)
• พื้นที่: O(k) สำหรับผลลัพธ์ (O(1) เพิ่มเติม)

วิธีอื่น: Two pointers จากกลาง, หรือ Heap (O(n log k)) แต่วิธี Binary Search นี้เร็วที่สุดและสวยงามที่สุดสำหรับอาร์เรย์ที่เรียงลำดับแล้ว