数据结构
网络
关系数据库管理系统 (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 次浏览
广告