K giá trị mạnh nhất trong mảng (The k Strongest Values in an Array) trong C++

Cho mảng arr và số nguyên k. Giá trị arr[i] mạnh hơn arr[j] nếu |arr[i] - m| > |arr[j] - m| với m là trung vị. Nếu bằng nhau, giá trị lớn hơn mạnh hơn. Tìm k giá trị mạnh nhất.

Ví dụ

Đầu vào: arr = [1,2,3,4,5], k = 2
Đầu ra: [5,1] (trung vị 3, thứ tự mạnh: 5,1,4,2,3).

Thuật toán hai con trỏ sau khi sắp xếp

1. Sắp xếp mảng.
2. Trung vị m = arr[(n-1)/2].
3. Hai con trỏ i=0 (nhỏ nhất), j=n-1 (lớn nhất).
4. Lặp k lần:
   • So sánh |arr[j]-m| và |arr[i]-m|.
   • Nếu bên phải mạnh hơn hoặc bằng → lấy arr[j--].
   • Ngược lại → lấy arr[i++].

Triển khai C++

#include <bits/stdc++.h>
using namespace std;

class Solution {
public:
    vector<int> getStrongest(vector<int>& arr, int k) {
        sort(arr.begin(), arr.end());
        int n = arr.size(), m = arr[(n-1)/2];
        int i = 0, j = n - 1;
        vector<int> res;
        while (k--) {
            int d1 = abs(arr[j] - m), d2 = abs(arr[i] - m);
            if (d1 >= d2) res.push_back(arr[j--]);
            else res.push_back(arr[i++]);
        }
        return res;
    }
};

Độ phức tạp

• Thời gian: O(N log N) do sắp xếp.
• Không gian: O(1) thêm (không tính kết quả).

Kết quả kiểm thử

Đầu vào: {1,2,3,4,5}, 2
Đầu ra: [5, 1]