資料結構
網路
關係資料庫管理系統 (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 次瀏覽
廣告