অ্যারেতে প্রতিটি উপাদানের জন্য সবচেয়ে কাছের বড় মান খুঁজে বের করা C++-তে

এখানে আমরা দেখব কিভাবে অ্যারেতে প্রতিটি উপাদানের জন্য সবচেয়ে কাছের বড় মান খুঁজে বের করা যায়। যদি একটি উপাদান x-এর পরের উপাদানটি তার চেয়ে বড় হয় এবং অ্যারেতে উপস্থিত থাকে, তবে সেটিই সেই উপাদানের আঁকা বড় মান হবে। যদি উপাদানটি না থাকে, তবে -1 রিটার্ন করুন। মনে করুন অ্যারে উপাদানগুলো হল [10, 5, 11, 6, 20, 12], তবে আঁকা বড় উপাদানগুলো হবে [11, 6, 12, 10, -1, 20]। কারণ 20-এর অ্যারেতে কোনো বড় মান নেই, তাই -1 প্রিন্ট হবে।

এটি সমাধানের জন্য, আমরা C++ STL-র set ব্যবহার করব। সেট বাইনারি ট্রি পদ্ধতিতে ইমপ্লিমেন্টেড থাকে। বাইনারি ট্রিতে ইন-অর্ডার সাকসেসর সবসময় আঁকা বড় উপাদান। তাই আমরা O(log n) সময়ে উপাদানটি পেতে পারি।

উদাহরণ

#include <iostream>
#include <set>
using namespace std;

void nearestGreatest(int arr[], int n) {
    set<int> tempSet;
    for (int i = 0; i < n; i++)
        tempSet.insert(arr[i]);
    for (int i = 0; i < n; i++) {
        auto next_greater = tempSet.upper_bound(arr[i]);
        if (next_greater == tempSet.end())
            cout << -1 << " ";
        else
            cout << *next_greater << " ";
    }
}

int main() {
    int arr[] = {10, 5, 11, 6, 20, 12};
    int n = sizeof(arr) / sizeof(arr[0]);
    nearestGreatest(arr, n);
}

আউটপুট

11 6 12 10 -1 20