मान लीजिए हमारे पास 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।
इसे हल करने के लिए, हम निम्न चरणों का पालन करेंगे:
ऐरे arr को सॉर्ट करें
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, तो -
arr[j] को ret के अंत में डालें
(j को 1 से घटाएं)
अन्यथा
arr[i] को ret के अंत में डालें
(i को 1 से बढ़ाएं)
ret लौटाएं
उदाहरण
बेहतर समझ के लिए निम्न कार्यान्वयन देखें:
#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, ]
