একটি অ্যারে এবং k দেওয়া আছে। অ্যারেতে থেকে kটি সর্বোচ্চ এলিমেন্ট বের করুন, কিন্তু মুল অ্যারেতে যেই অর্ডারে আছে সেই অর্ডারে প্রিন্ট করুন।
উদাহরণ
ইনপুট: arr = {5,1,3,6,2}, k = 2
সর্বোচ্চ ২টি: 6, 5। মুল অর্ডারে: 5 আগে, তারপর 6।
আউটপুট: 5 6
অ্যালগরিদম
- অ্যারেকপি করে ডিসেন্ডিং সোর্ট করুন (
decArr)। decArr-র প্রথমkটি এলিমেন্ট হল টপ-কে এলিমেন্টগুলো।- মুল অ্যারে ট্রাভার্স করুন: যদি এলিমেন্ট টপ-কে সেটে থাকে, প্রিন্ট করুন।
C++ প্রোগ্রাম
#include <bits/stdc++.h>
using namespace std;
bool searchVal(int decArr[], int k, int ele) {
for (int i = 0; i < k; i++)
if (decArr[i] == ele) return true;
return false;
}
void printKMaxEle(int arr[], int k, int n) {
int decArr[n];
for (int i = 0; i < n; i++) decArr[i] = arr[i];
sort(decArr, decArr + n, greater());
for (int i = 0; i < n; ++i)
if (searchVal(decArr, k, arr[i]))
cout << arr[i] << " ";
}
int main() {
int arr[] = {15, 1, 3, 6, 2, 34, 8, 9};
int n = sizeof(arr)/sizeof(arr[0]);
int k = 3;
cout << k << " maximum elements of the array in their original order are \n";
printKMaxEle(arr, k, n);
return 0;
}
আউটপুট
3 maximum elements of the array in their original order are 15 34 9
ব্যাখ্যা
sort(..., greaterডিসেন্ডিং সোর্ট করে।()) searchValলিনিয়ার সার্চ করে (k ছোট হলে OK)।- বড়
k-এর জন্যunordered_setব্যবহার করুন O(1) লুকআপের জন্য।
অপ্টিমাইজড (Unordered Set)
void printKMaxEleOptimized(int arr[], int k, int n) {
vector decArr(arr, arr+n);
sort(decArr.begin(), decArr.end(), greater());
unordered_set topK(decArr.begin(), decArr.begin() + k);
for (int i = 0; i < n; i++)
if (topK.count(arr[i])) cout << arr[i] << " ";
}
কমপ্লেক্সিটি
| পদ্ধতি | টাইম | স্পেস |
|---|---|---|
| লিনিয়ার সার্চ | O(n log n + nk) | O(n) |
| Hash Set | O(n log n) | O(n) |
