C++の配列内のk個の最強の値

arrと呼ばれる数の配列と整数kがあるとします。 | arr [i] --m |の場合、値arr[j]よりも強いと言われる値arr[i]があります。> | 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増やします）

• 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, ]