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

相关文章

来自专栏King_3的技术专栏

leetcode-868-Binary Gap

Given a positive integer N, find and return the longest distance between two con...

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

Leetcode 19 Remove Nth Node From End of List 超简洁代码

Given a linked list, remove the nth node from the end of list and return its he...

1949
来自专栏calmound

Is It A Tree?(并查集)

判断树是否唯一 1.只有一个根节点,(1)在一棵树上一个根节点。1 2 3 2就是两个根节点(1)只有一棵树 2.不成环,入度不大于1 由于数组运行超界导致wa...

3186
来自专栏ml

南阳OJ----Binary String Matching

Binary String Matching 时间限制:3000 ms  |  内存限制:65535 KB 难度:3 描述Given two strings A...

29010
来自专栏技术小黑屋

Google IO:Android内存管理主题演讲记录

翻出了3年前的Google IO大会的主题演讲 Google IO 2011 Memory management for Android Apps,该演讲介绍...

711
来自专栏ml

uva----11729 Commando war (突击战争)

G Commando War Input: Standard Input Output: Standard Output “Wa...

2767
来自专栏和蔼的张星的图像处理专栏

112. 删除排序链表中的重复元素比较删除

给定一个排序链表,删除所有重复的元素每个元素只留下一个。 样例 给出 1->1->2->null,返回 1->2->null 给出 1->1->2->3-...

472
来自专栏聊聊技术

原 数据结构-散列表(Hash Table

3349
来自专栏技术小黑屋

Note for Google IO Memory Management for Android

This is the subtitle for Google I/O 2011: Memory management for Android Apps.

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

Uva 11729 Commando War (简单贪心)

Uva 11729  Commando War (简单贪心) There is a war and it doesn't look very promising...

2466

扫码关注云+社区