0719. Find K Th Smallest Pair Distance

719. Find K-th Smallest Pair Distance #

题目 #

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:

  1. 2 <= len(nums) <= 10000.
  2. 0 <= nums[i] < 1000000.
  3. 1 <= k <= len(nums) * (len(nums) - 1) / 2.

题目大意 #

给定一个整数数组,返回所有数对之间的第 k 个最小距离。一对 (A, B) 的距离被定义为 A 和 B 之间的绝对差值。

提示:

  1. 2 <= len(nums) <= 10000.
  2. 0 <= nums[i] < 1000000.
  3. 1 <= k <= len(nums) * (len(nums) - 1) / 2.

解题思路 #

  • 给出一个数组,要求找出第 k 小两两元素之差的值。两两元素之差可能重复,重复的元素之差算多个,不去重。
  • 这一题可以用二分搜索来解答。先把原数组排序,那么最大的差值就是 nums[len(nums)-1] - nums[0] ,最小的差值是 0,即在 [0, nums[len(nums)-1] - nums[0]] 区间内搜索最终答案。针对每个 mid,判断小于等于 mid 的差值有多少个。题意就转化为,在数组中找到这样一个数,使得满足 nums[i] - nums[j] ≤ mid 条件的组合数等于 k。那么如何计算满足两两数的差值小于 mid 的组合总数是本题的关键。
  • 最暴力的方法就是 2 重循环,暴力计数。这个方法效率不高,耗时很长。原因是没有利用数组有序这一条件。实际上数组有序对计算满足条件的组合数有帮助。利用双指针滑动即可计算出组合总数。见解法一。

代码 #


package leetcode

import (
	"sort"
)

func smallestDistancePair(nums []int, k int) int {
	sort.Ints(nums)
	low, high := 0, nums[len(nums)-1]-nums[0]
	for low < high {
		mid := low + (high-low)>>1
		tmp := findDistanceCount(nums, mid)
		if tmp >= k {
			high = mid
		} else {
			low = mid + 1
		}
	}
	return low
}

// 解法一 双指针
func findDistanceCount(nums []int, num int) int {
	count, i := 0, 0
	for j := 1; j < len(nums); j++ {
		for nums[j]-nums[i] > num && i < j {
			i++
		}
		count += (j - i)
	}
	return count
}

// 解法二 暴力查找
func findDistanceCount1(nums []int, num int) int {
	count := 0
	for i := 0; i < len(nums); i++ {
		for j := i + 1; j < len(nums); j++ {
			if nums[j]-nums[i] <= num {
				count++
			}
		}
	}
	return count
}


⬅️上一页

下一页➡️

Calendar Sep 6, 2020
Edit Edit this page
本站总访问量:  次 您是本站第  位访问者