C ++中数组中的k个最强值

假设我们有一个称为arr的数字数组和一个整数k。当| arr [i]-m |时，有一个值arr [i]比值arr [j]强。> | 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，做-

• 在ret的末尾插入arr [i]

• （将i增加1）

• 在ret的末尾插入arr [j]

• （将j减1）

• x1：= | arr [j]-m |

• x2：= | arr [i]-m |

• 如果x1> = x2，则-

• 除此以外

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