Java实现 LeetCode 719 找出第 k 小的距离对(二分搜索法+二分猜数字)
2023-09-14 08:58:02 时间
719. 找出第 k 小的距离对
给定一个整数数组,返回所有数对之间的第 k 个最小距离。一对 (A, B) 的距离被定义为 A 和 B 之间的绝对差值。
示例 1:
输入:
nums = [1,3,1]
k = 1
输出:0
解释:
所有数对如下:
(1,3) -> 2
(1,1) -> 0
(3,1) -> 2
因此第 1 个最小距离的数对是 (1,1),它们之间的距离为 0。
提示:
2 <= len(nums) <= 10000.
0 <= nums[i] < 1000000.
1 <= k <= len(nums) * (len(nums) - 1) / 2.
PS:
二分搜索法,去猜那个数字,然后再去找
class Solution {
public int smallestDistancePair(int[] nums, int k) {
Arrays.sort(nums);
int lo = 0;
int hi = nums[nums.length - 1] - nums[0];
while (lo < hi) {
int mi = (lo + hi) / 2;
int count = 0;
int left = 0;
for (int right = 0; right < nums.length; ++right) {
while (nums[right] - nums[left] > mi) {
left++;
}
count += right - left;
}
if (count >= k) {
hi = mi;
} else {
lo = mi + 1;
}
}
return lo;
}
}
相关文章
- java 取余 小数_Java小数取余问题求助「建议收藏」
- java pfx 证书_Java将pfx证书转换为jks[通俗易懂]
- java启动器_JAVA基础:Java 启动器如何查找类
- java怎么用_如何使用Java编写程序
- 九九乘法表java代码_java怎么实现九九乘法表
- java jersey使用总结_jersey Java Jersey配置「建议收藏」
- 【说站】java注解有哪些作用
- JAVA入门学习三
- Java面试-基础篇
- java socket详解_Java Socket 编程原理及教程「建议收藏」
- 反编译Java_java反编译的代码可以修改么
- java服装销售系统ssm
- Java技术专家成长路线总结(思维导图)
- 面试:Java 到底是值传递还是引用传递?
- Java MongoDAO 初始化详解大数据
- Java学习笔记之九java二维数组及其多维数组的内存应用拓展延伸详解编程语言
- Java学习笔记之七java函数的语法规则总结详解编程语言
- java I/O之装饰者模式详解编程语言
- Java的整个字符串的结束索引在最后一个字符之外详解编程语言
- Linux下Java开发入门指南(linux下java开发)
- Java多线程(九)—— interrupt()和线程终止方式详解编程语言
- Java调用Redis实现高性能数据存储(java调用redis)
- 数据解决Redis和Java中数据过期问题(redisjava过期)
- 如何在Linux系统下成功安装Java?(linux下安装java)
- Linux下开发靠谱的Java应用(linux基于java)
- 一文快速回顾 Java 操作数据库的方式-JDBC
- 浅析java中Integer传参方式的问题
- java对象序列化与反序列化的默认格式和json格式使用示例