JavaInterview JavaInterview
首页
指南
分类
标签
归档
  • CSDN (opens new window)
  • 文档集合 (opens new window)
  • 系统架构 (opens new window)
  • 微信号 (opens new window)
  • 公众号 (opens new window)

『Java面试+Java学习』
首页
指南
分类
标签
归档
  • CSDN (opens new window)
  • 文档集合 (opens new window)
  • 系统架构 (opens new window)
  • 微信号 (opens new window)
  • 公众号 (opens new window)
  • 指南
  • 简历

  • Java

  • 面试

  • 算法

  • algorithm
  • leetcode
JavaInterview.cn
2022-10-05
目录

找出第 K 小的数对距离Java

文章发布较早,内容可能过时,阅读注意甄别。

# 题目

数对 (a,b) 由整数 a 和 b 组成,其数对距离定义为 a 和 b 的绝对差值。

给你一个整数数组 nums 和一个整数 k ,数对由 nums[i] 和 nums[j] 组成且满足 0 <= i < j < nums.length 。返回 所有数对距离中 第 k 小的数对距离。

示例 1:

输入:nums = [1,3,1], k = 1
输出:0
解释:数对和对应的距离如下:
(1,3) -> 2
(1,1) -> 0
(3,1) -> 2
距离第 1 小的数对是 (1,1) ,距离为 0 。

示例 2:

输入:nums = [1,1,1], k = 2
输出:0

示例 3:

输入:nums = [1,6,1], k = 3
输出:5

提示:

  • n == nums.length
  • 2 <= n <= 104
  • 0 <= nums[i] <= 106
  • 1 <= k <= n * (n - 1) / 2

# 思路

二分查找

# 解法


class Solution {
    public int smallestDistancePair(int[] nums, int k) {

        Arrays.sort(nums);
        //最小的数对和最大的数对
        int l = 0, r = nums[nums.length-1] - nums[0];
        //二分查找答案
        while(l < r){
            int mid = (l + r) >> 1;
            if(getCnt(nums, mid) >= k){
                r = mid;
            }else{
                l = mid + 1;
            }
        }
        return l;
    }
    int getCnt(int[] nums, int val){
        //统计数对个数
        int ans = 0, left = 0;
        for(int i = 0; i < nums.length; i++){
            while(left < i && nums[i] - nums[left] > val)left++;
            ans += i - left;
        }
        return ans;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

# 总结

  • 分析出几种情况,然后分别对各个情况实现
微信 支付宝
最近更新
01
1633. 各赛事的用户注册率 Java
07-02
02
1636. 按照频率将数组升序排序 Java
07-02
03
1639. 通过给定词典构造目标字符串的方案数 Java
07-02
更多文章>
Theme by Vdoing | Copyright © 2019-2025 JavaInterview.cn
  • 跟随系统
  • 浅色模式
  • 深色模式
  • 阅读模式