nটি রেঞ্জ (ইনক্লूसিভ) এবং একটি পূর্ণসংখ্যা k দেওয়া আছে। সব রেঞ্জের সংখ্যাগুলো একসাথে মিলিয়ে (সোর্টেড أور্ডারে) k-তম স্মলেস্ট এলিমেন্ট বের করতে হবে।
উদাহরণ
ইনপুট: ranges = {{2,5}, {7,9}, {12,15}}, k = 9
মার্জড অ্যারে: {2,3,4,5, 7,8,9, 12,13,14,15}
৯ম এলিমেন্ট (০-বেসড? ১-বেসড? কোডে ০-বেসড ব্যবহৃত): 13
অ্যালগরিদম: মার্জড অ্যারে বানানো (সিম্পল)
- সব রেঞ্জ থেকে সংখ্যা পুশ করে একটি বড় অ্যারে বানান।
- রেঞ্জগুলো ইতিমধ্যে সোর্টেড, তাই মার্জড অ্যারেও সোর্টেড থাকবে।
k-তম ইনডেক্স এক্সেস করুন।
C++ প্রোগ্রাম
#include <iostream>
using namespace std;
int main() {
int arr[][2] = {{2,5}, {7,9}, {12,15}};
int n = sizeof(arr)/sizeof(arr[0]);
int k = 9;
int rangeArr[1000];
int size = 0;
for (int i = 0; i < n; i++)
for (int j = arr[i][0]; j <= arr[i][1]; j++) {
rangeArr[size] = j;
size++;
}
if (k < size)
cout << k << "th smallest element of the ranged array is " << rangeArr[k] << endl;
else
cout << "invalid Index";
return 0;
}
আউটপুট
9th smallest element of the ranged array is 13
ব্যাখ্যা
- কোডে
k০-বেসড হিসেবে ব্যবহার করা হয়েছে (rangeArr[k])। - যদি কোয়েরি ১-বেসড হয়, তবে
rangeArr[k-1]ব্যবহার করুন। - টাইম:
O(Total Elements), স্পেস:O(Total Elements)।
ইফিশিয়েন্ট পদ্ধতি (বাইনারি সার্চ, O(n log MaxVal))
মার্জড অ্যারে বানানো ছাড়া, ভ্যালু রেঞ্জে বাইনারি সার্চ করুন: মিড ভ্যালু চেক করুন কত এলিমেন্ট ≤ মিড।
// পসুডো
low = minStart, high = maxEnd
while (low <= high) {
mid = (low+high)/2
count = sum over ranges of max(0, min(mid, end) - start + 1)
if (count >= k) ans = mid, high = mid-1
else low = mid+1
}
এটি বড় রেঞ্জ/বড় কাউন্টের জন্য প্রয়োজনীয়।
