Tìm hiệu nhỏ thứ k của các cặp phần tử trong mảng (C++)

Cho mảng số nguyên, tìm hiệu tuyệt đối giữa mọi cặp, sắp xếp, lấy giá trị thứ k (0-indexed).

Ví dụ

Đầu vào: numbers = {2, 6, 4, 8}, k = 2

Đầu ra: 2

Giải thích: Các cặp: (2,6)=4, (2,4)=2, (2,8)=6, (6,4)=2, (6,8)=2, (4,8)=4. Sắp xếp: 2,2,2,4,4,6. Phần tử index 2 = 2.

Phương pháp: Binary Search + Two Pointers (O(N log MaxVal))

• Sort mảng.
• Binary search đáp án mid trong [0, max-min].
• Đếm số cặp có hiệu ≤ mid: dùng 2 con trỏ lp, duyệt i, tăng lp cho đến khi a[i]-a[lp] <= mid. Cộng i-lp.
• Nếu count ≥ k+1 → thu hẹp phải, ngược lại thu hẹp trái.

Ví dụ mã C++

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

int kthSmallestDifference(vector& a, int k) {
    k++; // 1-indexed cho dễ so sánh
    sort(a.begin(), a.end());
    int lo = 0, hi = a.back() - a[0];
    while (lo < hi) {
        int mid = lo + (hi - lo) / 2;
        long long cnt = 0;
        int lp = 0;
        for (int i=1; i mid) lp++;
            cnt += i - lp;
        }
        if (cnt >= k) hi = mid;
        else lo = mid + 1;
    }
    return lo;
}

int main() {
    vector nums = {2, 6, 4, 8};
    cout << kthSmallestDifference(nums, 2) << endl; // 2
    return 0;
}

Đầu ra chương trình

2