मान लीजिए कि हमारे पास एआर नामक संख्याओं की एक सरणी है और एक पूर्णांक 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 :=गिरफ्तारी का आकार
-
मी :=एआर [(एन -1)/2]
-
जोड़े की एक सरणी v परिभाषित करें
-
मैं :=0, जे :=n - 1
-
एक सरणी रिट परिभाषित करें
-
जबकि k गैर-शून्य है, प्रत्येक पुनरावृत्ति में k घटाएं, −
. करें-
x1 :=|arr[j]- m|
-
x2 :=|arr[i]- m|
-
यदि x1>=x2, तो -
-
रिट के अंत में arr[j] डालें
-
(j को 1 से घटाएं)
-
-
अन्यथा
-
रिट के अंत में 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, ]
