ধরুন আমাদের কাছে arr এবং একটি পূর্ণসংখ্যা k নামক একটি অ্যারে আছে। একটি মান arr[i] আছে যেটিকে arr[j] মানের চেয়ে শক্তিশালী বলা হয় যখন |arr[i] - m|> |arr[j] - m| যেখানে m হল অ্যারের মধ্যমা। যদি |arr[i] - m| |arr[j] - m| এর মতই, তারপর arr[i] কে arr[j] এর চেয়ে শক্তিশালী বলা হয় যদি arr[i]> arr[j] হয়। তাই আমাদের অ্যারের সবচেয়ে শক্তিশালী k মানের একটি তালিকা খুঁজে বের করতে হবে।
সুতরাং, যদি ইনপুট হয় arr =[1,2,3,4,5], k =2, তাহলে আউটপুট হবে [5,1], এর কারণ হল মধ্যমা 3, এবং অ্যারের উপাদানগুলি সাজানো হয়েছে শক্তিশালী দ্বারা হয় [5,1,4,2,3]. এখানে শক্তিশালী 2টি উপাদান হল [5, 1]। [1, 5]ও বৈধ। যদিও |5 - 3| |1 - 3| এর মত কিন্তু 5 1 থেকে শক্তিশালী কারণ 5> 1।
এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -
-
অ্যারে অ্যারে সাজান
-
n :=arr এর আকার
-
m :=arr[(n - 1)/2]
-
জোড়ার একটি অ্যারে v সংজ্ঞায়িত করুন
-
i :=0, j :=n - 1
-
একটি অ্যারে ret সংজ্ঞায়িত করুন
-
যখন k অ-শূন্য, প্রতিটি পুনরাবৃত্তিতে k হ্রাস করুন, −
করুন-
x1 :=|arr[j]- m|
-
x2 :=|arr[i]- m|
-
x1>=x2 হলে −
-
ret এর শেষে arr[j] ঢোকান
-
(j 1 দ্বারা কমিয়ে দিন)
-
-
অন্যথায়
-
ret এর শেষে arr[i] ঢোকান
-
(i 1 দ্বারা বাড়ান)
-
-
-
রিটার্ন রিটার্ন
উদাহরণ
আরো ভালোভাবে বোঝার জন্য নিচের বাস্তবায়নটি দেখি -
#include <bits/stdc++.h>
using namespace std;
void print_vector(vector<int> v){
cout << "[";
for(int i = 0; i<v.size(); i++){
cout << v[i] << ", ";
}
cout << "]"<<endl;
}
class Solution {
public:
int calc(int x, int m){
return abs(x - m);
}
vector<int> getStrongest(vector<int>& arr, int k) {
sort(arr.begin(), arr.end());
int n = arr.size();
int m = arr[(n - 1) / 2];
vector<pair<int, int> > v;
int i = 0;
int j = n - 1;
vector<int> ret;
while (k--) {
int x1 = calc(arr[j], m);
int x2 = calc(arr[i], m);
if (x1 >= x2) {
ret.push_back(arr[j]);
j--;
}
else {
ret.push_back(arr[i]);
i++;
}
}
return ret;
}
};
main(){
Solution ob;
vector<int> v = {1,2,3,4,5};
print_vector(ob.getStrongest(v,2));
} ইনপুট
{1,2,3,4,5},2 আউটপুট
[5, 1, ]
