草庐IT

LeetCode：719. 找出第 K 小的数对距离

alex很累 2023-09-14 原文

问题链接

719. 找出第 K 小的数对距离

问题描述

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

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

提示：

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

示例

示例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

解题思路

看一下提示的范围，就知道暴力破解直接没戏~
这道题，可以对数对距离的域值进行二分查找解题。

  1. 先对数组nums排序；
  2. 对数对距离的域值进行二分查找：
    A. 初始left为0，right为数组头尾相减的绝对值，middle为left与right和的一半；
    B. 统计所有距离小于等于 middle 的数对数量，记为count；
    C. 如果count大于等于k，right = middle - 1；反之，left = middle + 1；
    D. 如果left小于等于right，继续以上操作；
  3. 当left大于right时，返回结果left。

代码示例（JAVA）

class Solution {
    public int smallestDistancePair(int[] nums, int k) {
        // 先进行排序
        Arrays.sort(nums);

        // 值域二分找k
        int length = nums.length;
        int left = 0, right = nums[length - 1] - nums[0];
        while (left <= right) {
            int middle = (right + left) / 2;
            int count = countPair(nums, middle);
            if (count >= k) {
                right = middle - 1 ;
            } else {
                left = middle + 1;
            }
        }

        return left;
    }

    // 统计数对
    public int countPair(int[] nums, int value) {
        int count = 0;
        for (int i = 0; i < nums.length - 1; i++) {
            for (int j = i + 1; j < nums.length; j++) {
                if (nums[j] - nums[i] <= value) {
                    count++;
                } else {
                    break;
                }
            }
        }

        return count;
    }
}

执行结果

找出LeetCodecodenumsleft

有关LeetCode：719. 找出第 K 小的数对距离的更多相关文章

  1. Python 刷Leetcode题库，顺带学英语单词（31） - 2

    ValidPalindromeGivenastring,determineifitisapalindrome,consideringonlyalphanumericcharactersandignoringcases. [#125]Example:"Aman,aplan,acanal:Panama"isapalindrome."raceacar"isnotapalindrome.Haveyouconsiderthatthestringmightbeempty?Thisisagoodquestiontoaskduringaninterview.Forthepurposeofthisproblem

  2. ruby - 是否有内置的 Ruby 1.8.7 将数组拆分为相同大小的子数组？ - 2

    我已经开始了:defsplit_array(array,size)index=0results=[]ifsize>0whileindex如果我在[1,2,3,4,5,6]上运行它，比如split_array([1,2,3,4,5,6],3)它将产生这个数组:[[1,2,3],[4,5,6]]。在Ruby1.8.7中是否已经有可用的东西可以做到这一点？ 最佳答案 [1,2,3,4,5,6].each_slice(3).to_a#=>[[1,2,3],[4,5,6]]对于1.8.6:require'enumerator'[1,2,3,4

  3. ruby-on-rails - 如何找出拦截 'method_missing' 的内容 - 2

    使用Ruby1.8.6/Rails2.3.2我注意到在我的任何ActiveRecord模型类上调用的任何方法都返回nil而不是NoMethodError。除了烦人之外，这还破坏了动态查找器(find_by_name、find_by_id等)，因为即使存在记录，它们也总是返回nil。不从ActiveRecord::Base派生的标准类不受影响。有没有办法追踪在ActiveRecord::Base之前拦截method_missing的是什么？更新:切换到1.8.7后，我发现(感谢@MichaelKohl)will_paginate插件首先处理method_missing。但是will_pa

  4. IDEA使用LeetCode插件 - 2

    前言我们习惯用idea编写、调试代码，在LeetCode上刷题时，如果能够在IDEA编写代码，并且做好代码管理，是一件事半功倍的事情。对于后续复习题目，做笔记也会非常便利。本文目的在于介绍LeetCodeEditor的使用，以及配置工具类，最终目录结构如下：note：放置笔记src：放置代码leetcode.editor.cn：插件LeetCodeEditor自动生成utils：自定义的工具包，可用于自动化输入测试用例，定义题目需要的类（结构体）out：运行测试时自动生成LeetCodeEditorGitHub：https://github.com/shuzijun/leetcode-edit

  5. 最新版人脸识别小程序 图片识别 生成二维码签到 地图上选点进行位置签到 计算签到距离 课程会议活动打卡日常考勤 上课签到打卡考勤口令签到 - 2

    技术选型1，前端小程序原生MINA框架cssJavaScriptWxml2，管理后台云开发Cms内容管理系统web网页3，数据后台小程序云开发云函数云开发数据库（基于MongoDB）云存储4，人脸识别算法基于百度智能云实现人脸识别一，用户端效果图预览老规矩我们先来看效果图，如果效果图符合你的需求，就继续往下看，如果不符合你的需求，可以跳过。1-1，登录注册页可以看到登录页有注册入口，注册页如下我们的注册，需要管理员审核，审核通过后才可以正常登录使用小程序1-2，个人中心页登录成功以后，我们会进入个人中心页我们在个人中心页可以注册人脸，因为我们做人脸识别签到，需要先注册人脸才可以进行人脸比对，进

  6. ruby - 如何找出所有数组元素是否都符合某个条件？ - 2

    我有一个大数组，我需要知道它的所有元素是否都能被2整除。我是这样做的，但是有点丑:_true=truearr.each{|e|(e%2).zero?||_true=false}if_true==true#...end如何在没有额外循环/赋值的情况下做到这一点？ 最佳答案 这样就可以了。arr.all?(&:even?) 关于ruby-如何找出所有数组元素是否都符合某个条件？，我们在StackOverflow上找到一个类似的问题： https://stackov

  7. ruby-on-rails - 将大型 Rails 应用程序分解成较小的应用程序？ - 2

    按照目前的情况，这个问题不适合我们的问答形式。我们希望答案得到事实、引用或专业知识的支持，但这个问题可能会引发辩论、争论、投票或扩展讨论。如果您觉得这个问题可以改进并可能重新打开，visitthehelpcenter指导。关闭10年前。我有一个包含600个模型的Rails应用程序，很快就会增加到800-1000个。我想对Rails应用程序进行分段，以便仅加载某些模型，因此充当单独的应用程序，但所有模型都共享相同的基本模型。是否有执行此操作的标准做法？编辑:我在2.3.8编辑2:问题是许多模型是相似的，但不同之处恰恰足以保证编写一个新类，也就是说，将所有模型都放在一个模型中所需的逻辑将是

  8. ruby - 在 Elasticsearch 中计算地理距离 - 2

    我在查询中使用geo_distancefilter和tire，它工作正常:search.filter:geo_distance,:distance=>"#{request.distance}km",:location=>"#{request.lat},#{request.lng}"我预计结果会以某种方式包括到我用于过滤器的地理位置的计算距离。有没有办法告诉elasticsearch在响应中包含它，这样我就不必在ruby​​中为每个结果计算它？==更新==我在谷歌群组中的foundtheanswer:search.sortdoby"_geo_distance","location"=>"

  9. ruby - 从 Gemfile 中找出哪些 gems 需要 native c 扩展？ - 2

    我最近才开始将注意力转移到在TorqueBox上部署Ruby应用程序，这当然是在Jruby上构建的。到目前为止，我基本上一直在执行bundleinstall，然后在通往jrubydom的过程中处理每个gem，但我遇到了几个gem，由于需要重新实现大型他们的一部分。有没有一种方法可以调用bundler或ruby​​gems来遍历所有gem及其deps以测试它们是否需要nativec扩展，然后返回这样一个列表？处理一些更小的项目，或者甚至知道是否值得处理一个项目，将它转移到jruby肯定会很好。 最佳答案 基于具有原生扩展的gems通常

  10. Ruby:Titleize:如何忽略较小的词，如 'and' 、 'the' 、 'or 等 - 2

    deftitleize(string)string.split("").map{|word|word.capitalize}.join("")end这会标题化每个单词，但我如何捕捉某些我不想大写的单词？即)jack和吉尔请不要使用正则表达式。更新:我在使这段代码工作时遇到了问题:我让它打印了一个全部大写的单词数组，但并非没有下面的列表。words_no_cap=["and","or","the","over","to","the","a","but"]deftitleize(string)cap_word=string.split("").map{|word|word.capitali

随机推荐