数据结构
网络
关系型数据库管理系统
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化学
生物
数学
英语
经济学
心理学
社会学
时尚研究
法律研究C++ 中数组中 k 个最强值
假设我们有一个名为 arr 的数字数组和一个整数 k。当 |arr[i] - m| > |arr[j] - m| 时，一个值 arr[i] 被认为比一个值 arr[j] 更强，其中 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。
为了解决这个问题，我们将遵循以下步骤 -
对数组 arr 进行排序
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，则 -
将 arr[j] 插入到 ret 的末尾
(将 j 减 1)
否则
将 arr[i] 插入到 ret 的末尾
(将 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, ]
更新于: 2020年11月18日
168 次查看
广告