資料結構
網路
關係資料庫管理系統 (RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝設計
法學C++程式：查詢陣列中所有元素對的第k小差異
假設我們得到一個包含多個整數的列表。我們需要找出陣列中每對值的差，並找出第k小的差值。索引從0開始，k值作為輸入給出。
因此，如果輸入類似於 numbers = {2, 6, 4, 8}，k = 2，則輸出將為2。
各對之間的差異為：
(2, 6) = 4
(2, 4) = 2
(2, 8) = 6
(6, 4) = 2
(6, 8) = 2
(4, 8) = 4
如果我們對值進行排序，它將變為 2, 2, 2, 4, 4, 6。第2小的值是2。（索引從0開始）。
為了解決這個問題，我們將遵循以下步驟：
- 將k加1
- 對輸入陣列排序
- le := 0
- ri := 輸入的最後一個元素 - 輸入的第一個元素
- 當 le < ri 時，執行：
- mid := (le + ri) / 2
- tmp := 0
- lp := 0
- 初始化 i := 1，當 i < 輸入大小，更新（i 加 1），執行：
- 當 input[i] - input[lp] > mid 時，執行：
- lp := lp + 1
- tmp := tmp + i - lp
- 當 input[i] - input[lp] > mid 時，執行：
- 如果 tmp >= k，則：
- ri := mid
- 否則
- le := mid + 1
- 返回 le
示例
讓我們看看下面的實現，以便更好地理解：
#include<bits/stdc++.h>
using namespace std;
int solve(vector<int>& input, int k) {
k++;
sort(input.begin(), input.end());
int le = 0;
int ri = input.back() - input[0];
while (le < ri) {
int mid = (le + ri) / 2;
long long tmp = 0;
int lp = 0;
for (int i = 1; i < input.size(); i++) {
while (input[i] - input[lp] > mid) lp++;
tmp += i - lp;
}
if (tmp >= k)
ri = mid;
else
le = mid + 1;
}
return le;
}
int main() {
vector<int> numbers = {2, 6, 4, 8};
cout<< solve(numbers, 2) <<endl;
return 0;
}輸入
vector<int> numbers = {2, 6, 4, 8};
cout<< solve(numbers, 2) <<endl;輸出
2
更新於：2021年10月19日
315 次瀏覽
廣告