数据结构
网络
关系数据库管理系统 (RDBMS)
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装学
法学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
- for i := 0 to n-1 do −
- x := max(x, nums[i])
- 定义一个大小为x + 1的数组cnt
- for i := 0 to n-1 do −
- for j := i + 1 to n-1 do −
- cnt[|nums[j] - nums[i]|] += 1
- for j := i + 1 to n-1 do −
- for i := 0 to x do −
- if cnt[i] >= k then −
- return i
- k := k - cnt[i]
- if cnt[i] >= k then −
- return 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
更新于：2020年6月2日
206 次浏览
广告