假设我们得到一个包含几个整数的列表。我们必须找出数组中每对值之间的差异,并找出第 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 开始)。
让我们看看以下实现以获得更好的理解 -
#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