在C ++中找到第K个最小的配对距离

假设我们有一个整数数组；我们必须找到所有对中的第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，当i <n时，更新（将i增加1），执行-

• x：= x和nums的最大值[i]

• 定义大小为x + 1的数组cnt

• 对于初始化i：= 0，当i <n时，更新（将i增加1），执行-

• 将cnt [| nums [j]-nums [i] |]增加1

• 对于初始化j：= i + 1，当j <n时，更新（将j增加1），-

• 对于初始化i：= 0，当i <= x时，更新（将i增加1），执行-

• 还给我

• 如果cnt [i]> = k，则-

• k：= k-cnt [i]

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

输入值

{1,3,8}

输出结果

5