ค่า k ค่าที่แข็งแกร่งที่สุดในอาร์เรย์ใน C++

สมมติว่าเรามีอาร์เรย์ตัวเลข arr และจำนวนเต็ม k ค่า arr[i] ถือว่า "แข็งแกร่งกว่า" arr[j] เมื่อ |arr[i] - m| > |arr[j] - m| โดย m คือ median ของอาร์เรย์ หากระยะห่างเท่ากัน ค่าที่มากกว่าจะแข็งแกร่งกว่า เราต้องหา k ค่าที่แข็งแกร่งที่สุด

ตัวอย่าง: arr = [1,2,3,4,5], k = 2 median = 3 เรียงตามความแข็งแกร่ง: [5,1,4,2,3] ผลลัพธ์: [5,1]

วิธีแก้ปัญหา

1. เรียงอาร์เรย์ arr
2. หา median m = arr[(n-1)/2]
3. ใช้ two-pointer: i ชี้ซ้าย, j ชี้ขวา
4. เปรียบเทียบ |arr[j]-m| กับ |arr[i]-m| ใส่ค่าที่แข็งแกร่งกว่า
5. ทำซ้ำ k ครั้ง

ตัวอย่างโค้ด C++

#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]; 
        int i = 0, 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; 
    } 
}; 

int 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, ]