在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
以上是 在C ++中找到第K个最小的配对距离 的全部内容, 来源链接: utcz.com/z/340870.html