用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。 （索引從 0)。

為了解決這個問題，我們將按照以下步驟操作-

• 將k 增加1
• 對數組輸入進行排序
• le : = 0
• ri := 輸入的最後一個元素- 輸入的第一項
• while le
• mid := (le ri) / 2
• tmp := 0
• lp := 0
• 用於初始化i := 1 ，當i
• #while input[i] - input[lp] > mid，執行−
  • lp := lp 1
• tmp := tmp i - lp

如果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

以上是用C++寫一個程序，找出數組中所有元素對之間第k小的差值的詳細內容。更多資訊請關注PHP中文網其他相關文章！