สมมติว่าเรามีอาร์เรย์ของตัวเลขที่เรียกว่า arr และจำนวนเต็ม k มีค่า arr[i] ที่กล่าวว่าแข็งแกร่งกว่าค่า arr[j] เมื่อ |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 ของคู่
-
ผม :=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)
-
-
-
รีเทิร์น
ตัวอย่าง
ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -
#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, ]
