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