C++ में किसी सरणी में k सबसे मजबूत मान

मान लीजिए कि हमारे पास एआर नामक संख्याओं की एक सरणी है और एक पूर्णांक 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, ]