C++-এ Find K Closest Elements

এই সমস্যায় একটি সর্টেড অ্যারে, ইন্টিজার k এবং x দেওয়া থাকলে, x-এর সবচেয়ে নিকটবর্তী kটি এলিমেন্ট বের করতে হবে। ফলাফল অর্ডার করলে ইনক্রিজিং অর্ডারে হবে। টাই হলে ছোট এলিমেন্ট প্রাধান্য পাবে।

উদাহরণ: arr = [1,2,3,4,5], k=4, x=3 -> আউটপুট [1,2,3,4]।

সমাধানের পদ্ধতি (Binary Search on Window)

• উইন্ডোর আকার k। লেফট বাউন্ডারি low = 0, রাইট বাউন্ডারি high = n - k।
• বাইনারি সার্চ: mid = low + (high - low)/2।
  • যদি x - arr[mid] > arr[mid + k] - x, তবে উইন্ডো ডানে শিফট করুন (low = mid + 1)।
  • অন্যথায় বামে (high = mid)।
• low থেকে low + k - 1 পর্যন্ত এলিমেন্টগুলো আউটপুট করুন।

উদাহরণ (C++)

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

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

class Solution {
public:
    vector<int> findClosestElements(vector<int>& arr, int k, int x) {
        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;
        }
        return vector<int>(arr.begin() + low, arr.begin() + low + k);
    }
};

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

ইনপুট

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

আউটপুট

[1, 2, 3, 4]