C++-এ আইটেম-ভ্যালু লিস্ট থেকে kটি ন্যূনতম ভ্যালুর আইটেম বের করুন

আইটেম-ভ্যালু পেয়ারগুলোর একটি লিস্ট এবং k দেওয়া আছে। সবচেয়ে কম ভ্যালু वाले kটি আইটেম বের করতে হবে।

উদাহরণ

ইনপুট: { {"item1",200}, {"item2",100}, {"item3",500}, {"item4",400} }, k=2

আউটপুট: item4 (100), item2 (150) (সর্টেড অর্ডারে)

অ্যালগরিদম: সোর্ট + টপ-কে

1. ভেক্টর pair-এ স্টোর করুন।
2. ভ্যালু অনুযায়ী এসেন্ডিং সোর্ট করুন (টাই ব্রেক: নাম অনুযায়ী)।
3. প্রথম kটি এলিমেন্ট প্রিন্ট করুন।

C++ প্রোগ্রাম

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

bool compVal(pair A, pair B) {
    if (A.second == B.second) return A.first < B.first;
    return A.second < B.second;
}

int main() {
    int k = 2;
    vector> items;
    items.push_back({"item1", 350});
    items.push_back({"item2", 150});
    items.push_back({"item3", 500});
    items.push_back({"item4", 100});
    sort(items.begin(), items.end(), compVal);
    cout << k << " items with least value are \n";
    for (int i = 0; i < min((int)items.size(), k); ++i)
        cout << "Item : " << items[i].first << ", value : " << items[i].second << endl;
    return 0;
}

আউটপুট

2 items with least value are
Item : item4, value : 100
Item : item2, value : 150

ব্যাখ্যা

• compVal কাস্টম কমপেয়ারটর: প্রথমে ভ্যালু, তারপর নাম।
• sort O(n log n) টাইম নেয়।
• min(n,k) দিয়ে বাউন্ড চেক।

ইফিশিয়েন্ট: Min Heap / nth_element (O(n + k log n))

• nth_element দিয়ে k-তম ছোট ভ্যালু পার্টিশন করুন, তারপর সেটি সোর্ট করুন।
• বহুত বড় n এবং ছোট k-এর জন্য উপযোগী।

কমপ্লেক্সিটি