首页 > 试题广场 >

第 K 小的距离对

[编程题]第 K 小的距离对

给定一个长度为 n 的正整数数组 nums ，返回所有距离对中第 k 小的距离。

距离对定位为：两个数组下标 i , j 的差值的绝对值称为距离 $|nums_i-nums-j| \$

数据范围： $2 \le n \le 10^4 \$ ， $1 \le nums_i \le 10^6 \$ ， $1 \le k \le n\times(n-1)/2 \$

示例1

输入

[1,3,1,5],1

所有距离对有 （1，3） ， （1，1），（1，5） ，（3，1），（3，5），（1，5）。其中最小的是 (1,1) ，其距离是 0

示例2

[1,3,1,5],2

所有距离对有 （1，3） ， （1，1），（1，5） ，（3，1），（3，5），（1，5）。其中最小的是 （1，3）（其他距离2也是最小），其距离是 2

算法知识视频讲解

17c89

发表于 2024-11-15 12:00:29

import java.util.*; /** * NC408 第 K 小的距离对 * @author d3y1 */ public class Solution { /** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 * 展开全文

17c89

发表于 2024-09-08 15:19:05

二分排序双指针

难度：

2条回答 15收藏 2993浏览

查看代码

第 K 小的距离对

扫一扫，把题目装进口袋