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 条评论
登录 后参与评论

相关文章

来自专栏算法修养

POJ--3468 A Simple Problem with Integers(线段树)

A Simple Problem with Integers Time Limit: 5000MS Memory Limit: 131072K ...

3234
来自专栏数据结构与算法

RNQOJ [stupid]愚蠢的矿工(树形依赖背包)

$f[i][j] = max(f[i + 1][j - w[i]] + val[i], f[i + siz[rev[i]]][j]);$

764
来自专栏小樱的经验随笔

Codeforces 833D Red-black Cobweb【树分治】

D. Red-black Cobweb time limit per test:6 seconds memory limit per test:256 mega...

2443
来自专栏计算机视觉与深度学习基础

Leetcode 228. Summary Ranges

Given a sorted integer array without duplicates, return the summary of its rang...

1798
来自专栏数据结构与算法

cf567E. President and Roads(最短路计数)

首先确定哪些边一定在最短路上,一个条件是 从起点到该点的最短路 + 边权 + 从该点到终点的最短路 = 从起点到终点的最短路

742
来自专栏wym

Codeforces Round #483 (Div. 2) A. Game

Initially there are nn integers a1,a2,…,ana1,a2,…,an written on the board. Each ...

872
来自专栏听雨堂

一次数据库的整理的sql语句

//查询以井结束的记录 SELECT f_wellnumber, SUBSTRING(f_wellnumber, 1, LEN(f_wellnumber) - ...

1749
来自专栏算法修养

LeetCode 116 Populating Next Right Pointers in Each Node

Populate each next pointer to point to its next right node. If there is no next ...

622
来自专栏Jerry的SAP技术分享

面试问题 - 只用位操作在ABAP里实现a+b

算法描述参考我的SCN博客 Just for fun – Implement a + b using pure bitwise operation in ABA...

3765
来自专栏算法修养

HDU 3367 Pseudoforest(Kruskal)

Pseudoforest Time Limit: 10000/5000 MS (Java/Others)    Memory Limit: 65536/655...

2855

扫码关注云+社区