在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