หาระยะห่างคู่ที่ K น้อยที่สุด (Find K-th Smallest Pair Distance) ใน C++

ภาพรวมปัญหา

มีอาร์เรย์จำนวนเต็ม หาระยะห่าง (absolute difference) ของคู่ที่ K น้อยที่สุด ระยะห่างของคู่ (A, B) คือ |A - B|

ตัวอย่าง

[1, 3, 8] คู่ทั้งหมด: [1,3]=2, [3,8]=5, [1,8]=7 → k=2 → คำตอบ 5

แนวทางแก้ปัญหา (Counting Sort + Prefix Sum)

• หาค่าสูงสุด x ในอาร์เรย์
• นับความถี่ของแต่ละระยะห่างใน cnt[0..x]
• สะสม cnt แบบ prefix sum จนกว่าจะ ≥ k คืนค่าระยะห่างนั้น
• Complexity: O(n² + x) - เหมาะกับค่าไม่มาก

ตัวอย่างโปรแกรม

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

class Solution {
public:
    int smallestDistancePair(vector<int>& nums, int k) {
        int n = nums.size();
        int x = 0;
        for(int i = 0; i < n; i++) x = max(x, nums[i]);
        
        vector<int> cnt(x + 1);
        for(int i = 0; i < n; i++) {
            for(int j = i + 1; j < n; j++) {
                cnt[abs(nums[j] - nums[i])]++;
            }
        }
        
        for(int i = 0; i <= x; i++) {
            if(cnt[i] >= k) return i;
            k -= cnt[i];
        }
        return x;
    }
};

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

Input

{1,3,8}

Output

5