โปรแกรมหาความต่างคู่ที่ k-th น้อยที่สุดในอาร์เรย์ C++

ได้รับอาร์เรย์จำนวนเต็ม หาความต่างระหว่างทุกคู่ (pair) หาค่าที่ k-th น้อยที่สุด (index เริ่ม 0)

ตัวอย่าง

Input: numbers = {2, 6, 4, 8}, k = 2

Output: 2

คำอธิบาย: ความต่างคู่: (2,6)=4, (2,4)=2, (2,8)=6, (6,4)=2, (6,8)=2, (4,8)=4 → เรียง: 2,2,2,4,4,6 → index 2 = 2

อัลกอริทึม: Binary Search + Two Pointers

k++ (แปลงเป็น 1-based)
เรียงอาร์เรย์
Binary search คำตอบในช่วง [0, max-min]:
- mid = (le + ri) / 2
- นับจำนวนคู่ที่ diff ≤ mid ด้วย two pointers (lp):
  - วน i = 1..n-1: ขยับ lp จนกว่า input[i] - input[lp] ≤ mid
  - tmp += i - lp (จำนวนคู่ที่จบที่ i และ diff ≤ mid)
- ถ้า tmp ≥ k → ri = mid ไม่ → le = mid + 1
คืน le

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

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

int solve(vector<int>& input, int k) {
    k++;
    sort(input.begin(), input.end());
    int le = 0;
    int ri = input.back() - input[0];
    while (le < ri) {
        int mid = (le + ri) / 2;
        long long tmp = 0;
        int lp = 0;
        for (int i = 1; i < input.size(); i++) {
            while (input[i] - input[lp] > mid) lp++;
            tmp += i - lp;
        }
        if (tmp >= k) ri = mid;
        else le = mid + 1;
    }
    return le;
}

int main() {
    vector<int> numbers = {2, 6, 4, 8};
    cout << solve(numbers, 2) << endl;
    return 0;
}

Input

vector<int> numbers = {2, 6, 4, 8}; cout << solve(numbers, 2) << endl;