ค้นหาระยะทางคู่ที่เล็กที่สุดของ K-th ใน C++

สมมติว่าเรามีอาร์เรย์จำนวนเต็ม เราต้องหาระยะทางที่เล็กที่สุดที่ k ในบรรดาคู่ทั้งหมด ระยะห่างของคู่ (A, B) เป็นความแตกต่างที่แน่นอนระหว่าง A และ B ดังนั้นหากอินพุตเป็น [1,3,8] คู่ที่เป็นไปได้ทั้งหมดคือ [1,3], [3, 8] , [1, 8] ดังนั้นเมื่อ k =2 ระยะทางที่เล็กที่สุดเป็นอันดับสองคือ 5 (8 - 3)

เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -

• n :=ขนาดของ nums, x :=0
• สำหรับการเริ่มต้น i :=0 เมื่อฉัน
• x :=สูงสุดของ x และ nums[i]

ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -

ตัวอย่าง

#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;
   }
};
main(){
   Solution ob;
   vector<int> v = {1,3,8};
   cout << (ob.smallestDistancePair(v, 2));
}

อินพุต

{1,3,8}

ผลลัพธ์

5