arr이라는 숫자 배열과 정수 k가 있다고 가정합니다. |arr[i] - m|> |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보다 강합니다.
이 문제를 해결하기 위해 다음 단계를 따릅니다. −
-
배열 정렬 arr
-
n :=arr의 크기
-
m :=arr[(n - 1)/2]
-
쌍의 배열 v 정의
-
i :=0, j :=n - 1
-
ret 배열 정의
-
k가 0이 아닌 동안 각 반복에서 k를 감소시키고 -
-
x1 :=|arr[j]- m|
-
x2 :=|arr[i]- m|
-
x1>=x2이면 -
-
ret의 끝에 arr[j] 삽입
-
(j를 1만큼 감소)
-
-
그렇지 않으면
-
ret의 끝에 arr[i] 삽입
-
(i를 1씩 증가)
-
-
-
리턴 렛
예시
더 나은 이해를 위해 다음 구현을 살펴보겠습니다. −
#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, ]