Tìm khoảng cách cặp thứ K nhỏ nhất (Find K-th Smallest Pair Distance) trong C++

Cho mảng số nguyên, tìm khoảng cách tuyệt đối thứ k nhỏ nhất trong tất cả các cặp.

Ví dụ

nums = [1,3,8], k=2. Các cặp: (1,3)=2, (3,8)=5, (1,8)=7. Thứ 2 là 5.

Thuật toán đếm tần suất

Tìm max giá trị x. Mảng cnt[d] = số cặp có khoảng cách d. Duyệt mọi cặp O(n²) cập nhật cnt. Sau đó duyệt d từ 0, trừ k cho đến khi k ≤ cnt[d].

Chương trình C++

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

class Solution {
public:
    int smallestDistancePair(vector<int>& nums, int k) {
        int n = nums.size();
        int mx = *max_element(nums.begin(), nums.end());
        vector<int> cnt(mx+1, 0);
        for(int i=0; i= k) return d;
            k -= cnt[d];
        }
        return mx;
    }
};

int main() {
    Solution ob;
    vector<int> v = {1,3,8};
    cout << ob.smallestDistancePair(v, 2); // 5
    return 0;
}