Tìm khoảng cách cặp nhỏ nhất thứ K trong C ++

Giả sử chúng ta có một mảng số nguyên; chúng ta phải tìm khoảng cách nhỏ nhất thứ k trong số tất cả các cặp. Khoảng cách của một cặp (A, B) thực sự là sự khác biệt tuyệt đối giữa A và B. Vì vậy, nếu đầu vào giống như [1,3,8], thì tất cả các cặp có thể là [1,3], [3, 8] , [1, 8], thì khi k =2, khoảng cách nhỏ nhất thứ hai là 5 (8 - 3).

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

• n:=kích thước của nums, x:=0
• để khởi tạo i:=0, khi i
• x:=tối đa là x và nums [i]

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

Ví dụ

#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));
}

Đầu vào

{1,3,8}

Đầu ra

5