Java实现 LeetCode 719 找出第 k 小的距离对（二分搜索法+二分猜数字）

超、凢脫俗 2023-07-24 03:25 49阅读 0赞

## 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;
        }
     
    }

发表评论取消回复

表情：

评论列表（有 0 条评论，49人围观）

还没有评论，来说两句吧...

相关阅读

相关 LeetCode_二分搜索_中等_378. 有序矩阵中第 K 小的元素

目录 1.题目 2.思路 3.代码实现（Java） 1.题目给你一个 n x n 矩阵 matrix ，其中每行和每列元素均按升序排序，找到矩

素颜马尾好姑娘i/ 2023年10月06日 22:57/ 0 赞/ 97 阅读

相关 Java实现 LeetCode 719 找出第 k 小的距离对（二分搜索法+二分猜数字）

719. 找出第 k 小的距离对给定一个整数数组，返回所有数对之间的第 k 个最小距离。一对 (A, B) 的距离被定义为 A 和 B 之间的绝对差值。示例 1:

超、凢脫俗/ 2023年07月24日 03:25/ 0 赞/ 50 阅读

相关【分治法】二分搜索技术java实现

搜索问题问题描述：给定已按升序排好序的n个元素a\[0:n-1\]，搜索一特定元素x 要求：对该问题设计有效的求解算法，并分析算法在最坏情况的时间复杂性。顺序查

刺骨的言语ヽ痛彻心扉/ 2023年03月13日 11:40/ 0 赞/ 90 阅读

相关 OJ-leetcode-374. 猜数字大小（简单二分查找）

目录题目思路代码更优题解 -------------------- 题目猜数字游戏的规则如下：每轮游戏，我都会从 1 到 n 随机选择一

港控/mmm°/ 2022年12月26日 00:52/ 0 赞/ 310 阅读

相关 719 找出第 k 小的距离对（二分查找、双指针）

1. 问题描述：给定一个整数数组，返回所有数对之间的第 k 个最小距离。一对 (A，B) 的距离被定义为 A 和 B 之间的绝对差值。示例 1: 输入： nums

古城微笑少年丶/ 2022年09月09日 12:44/ 0 赞/ 222 阅读

相关二分搜索法

二分搜索法(C++) // //Description:二分搜索法 // include <iostream> using names

朱雀/ 2022年06月18日 01:55/ 0 赞/ 358 阅读

相关二分搜索

//二分查找的前提：有序序列 public static int binSearch(int[] arr,int number){

约定不等于承诺〃/ 2022年06月12日 13:38/ 0 赞/ 297 阅读

相关 leetcode 719. Find K-th Smallest Pair Distance 第k小的绝对距离 + 暴力计算真棒

Given an integer array, return the k-th smallest distance among all the pairs. The dista

朴灿烈づ我的快乐病毒、/ 2022年06月03日 09:41/ 0 赞/ 216 阅读

相关二分搜索

给定已经排好序的N个元素a\[0,m-1\],找到特定元素x 因为是拍好的序的N个元素，所以可以通过比较的方法不停的判断其属于哪个区间，通过二分每次只需在1/2区间里选择

矫情吗；*/ 2022年05月28日 03:29/ 0 赞/ 245 阅读

相关二分搜索树实现

二分搜索树是有顺序的树，某节点T的左子树都小于T节点，T的右子树均大于T节点的值。实现的关键代码为add操作，用递归很容易实现。 package tree;

﹏ヽ暗。殇╰゛Y/ 2022年04月27日 22:10/ 0 赞/ 334 阅读