Giả sử chúng ta có một mảng số gọi là arr và một số nguyên k. Có một giá trị arr [i] được cho là mạnh hơn một giá trị arr [j] khi | arr [i] - m |> | arr [j] - m | với m là trung vị của mảng. Nếu | arr [i] - m | giống với | arr [j] - m |, thì arr [i] được cho là mạnh hơn arr [j] nếu arr [i]> arr [j]. Vì vậy, chúng ta phải tìm một danh sách k giá trị mạnh nhất trong mảng.
Vì vậy, nếu đầu vào giống như arr =[1,2,3,4,5], k =2, thì đầu ra sẽ là [5,1], điều này là do trung vị là 3 và các phần tử của mảng được sắp xếp mạnh nhất là [5,1,4,2,3]. Ở đây 2 yếu tố mạnh nhất là [5, 1]. [1, 5] cũng hợp lệ. Mặc dù | 5 - 3 | giống như | 1 - 3 | nhưng 5 mạnh hơn 1 vì 5> 1.
Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -
-
sắp xếp mảng arr
-
n:=kích thước của arr
-
m:=arr [(n - 1) / 2]
-
Xác định một mảng v gồm các cặp
-
i:=0, j:=n - 1
-
Xác định ret mảng
-
trong khi k khác 0, giảm k trong mỗi lần lặp, thực hiện -
-
x1:=| arr [j] - m |
-
x2:=| arr [i] - m |
-
nếu x1> =x2, thì -
-
chèn arr [j] vào cuối ret
-
(giảm j đi 1)
-
-
Nếu không
-
chèn arr [i] vào cuối ret
-
(tăng i lên 1)
-
-
-
trả lại ret
Ví dụ
Hãy cùng chúng tôi xem cách triển khai sau đây để hiểu rõ hơn -
#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));
} Đầu vào
{1,2,3,4,5},2 Đầu ra
[5, 1, ]