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