এখানে দেখব অ্যারেতে প্রতিটি উপাদানের জন্য সবচেয়ে নিকটবর্তী বড় মান (closest greater value) কীভাবে বের করা যায়। উপাদান x-এর জন্য অ্যারেতে যদি তার চেয়ে বড় একটি উপাদান থাকে, তবে সেটি তার নিকটতম বড় মান। না থাকলে -1 রিটার্ন। অ্যারে [10, 5, 11, 6, 20, 12] হলে নিকটতম বড় মানগুলো: [11, 6, 12, 10, -1, 20]। ২০-র কোনো বড় মান নেই, তাই -1।
সমাধান: C++ STL-র set ব্যবহার করা হবে। set বাইনারি ট্রি (binary tree) দিয়ে ইমপ্লিমেন্টেড। বাইনারি ট্রিতে ইনঅর্ডার সাক্সেসর (inorder successor) সবসময় নিকটতম বড় উপাদান। তাই O(log n) টাইমে পাওয়া যাবে।
উদাহরণ
#include<iostream> #include<set> using namespace std; void nearestGreatest(int arr[], int n) { set 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
