LWC 56:719. Find K-th Smallest Pair Distance

LWC 56:719. Find K-th Smallest Pair Distance

传送门:719. Find K-th Smallest Pair Distance

Problem:

Given an integer array, return the k-th smallest distance among all the pairs. The distance of a pair (A, B) is defined as the absolute difference between A and B.

Example 1:

Input: nums = [1,3,1] k = 1 Output: 0 Explanation: Here are all the pairs: (1,3) -> 2 (1,1) -> 0 (3,1) -> 2 Then the 1st smallest distance pair is (1,1), and its distance is 0.

Note:

2 <= len(nums) <= 10000.

0 <= nums[i] < 1000000.

1 <= k <= len(nums) * (len(nums) - 1) / 2.

思路: 排序+二分+尺取法,实际上对数组排序后,小于某个数的对数可以在线性时间内求出(尺取法的思想),那么意味着问题需要猜值验证,所以二分,代码如下:

    public int smallestDistancePair(int[] nums, int k) {
        int n = nums.length;
        Arrays.sort(nums);
        int lf = -1;
        int rt = nums[n - 1] - nums[0];

        while (rt - lf > 1) {
            int mid = lf + (rt - lf) / 2;
            if (count(nums, mid) < k) {
                lf = mid;
            }
            else {
                rt = mid;
            }
        }
        return rt;
    }

    public int count(int[] nums, int mid) {  // <= mid 的个数
        int n = nums.length;
        int cnt = 0;

        int j = 0;

        for (int i = 1; i < n; ++i) {
            while (j < i && nums[i] - nums[j] > mid) j++;
            cnt += i - j;
        }

        return cnt;
    }   

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏菩提树下的杨过

javascript:json数据的页面绑定

web开发中,如果需要将“服务端返回的json对象”绑定到“现有页面上的dom元素”,传统赋值的方式太繁琐,写起来也很累(特别是json对象很大时),于是想出了...

1919
来自专栏老马说编程

(70) 原子变量和CAS / 计算机程序的思维逻辑

从本节开始,我们探讨Java并发工具包java.util.concurrent中的内容,本节先介绍最基本的原子变量及其背后的原理和思维。 原子变量 什么是原子...

1769
来自专栏佳爷的后花媛

由两个栈组成的队列2.由两个栈组成的队列

732
来自专栏后端之路

LinkedList源码解读

List中除了ArrayList我们最常用的就是LinkedList了。 LInkedList与ArrayList的最大区别在于元素的插入效率和随机访问效率 ...

21110
来自专栏Hellovass 的博客

设计一个有 getMin 功能的栈

这个类的设计上,采用两个栈,一个用来保存当前栈中的元素,其功能等同于一个正常的栈,记为 mStack;另一个栈用来保存每一步的最小值,记为 mMinStack.

622
来自专栏开发与安全

从零开始学C++之数据封装与抽象:分别用C和C++来实现一个链栈

下面通过分别用C和C++来实现一个链栈(链表实现),从中体会数据封装抽象的思想: C语言实现: #include <stdio.h> #include <std...

1920
来自专栏Hellovass 的博客

由两个栈组成的队列

栈的特点是先进后出,队列的特点是先进先出,使用两个栈正好能把顺序反过来实现类似队列的操作。

822
来自专栏流媒体

Prototype模式简介

用于创建重复的对象,同时又能保证性能。这种类型的设计模式属于创建型模式,它提供了一种创建对象的最佳方式。这种模式是实现了一个原型接口,该接口用于创建当前对象的克...

631
来自专栏我的技术专栏

数据结构图文解析之:栈的简介及C++模板实现

1475
来自专栏文武兼修ing——机器学习与IC设计

左式堆左式堆代码实现

左式堆 性质 零路径长 零路径长的定义为: 零路径长:从节点X到一个没有两个子节点的(有一个子节点或没有子节点)节点的最短距离 对于零路径长,有以下递归的...

27810

扫码关注云+社区