資料結構
網路
關係型資料庫管理系統
作業系統
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 次檢視
廣告