题目描述
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
.
题意:给定一个整数数组,返回所有数对之间的第 k 个最小距离。一对 (A, B) 的距离被定义为 A 和 B 之间的绝对差值。
算法1
(堆) $O(nlogk)$
题解1:堆,类似于第k
小分数的那一题(Leetcode 786),我们先将数组排好序,那么最小的pair
肯定是两个相邻的元素的最小值,此时对于固定的下标 i
,从小到大的距离分别为 (i, i + 1)
,(i, i + 2)
,…,(i, N - 1)
。因为 (i, j + 1)
的距离不会小于(i, j)
,因此如果 (i, j)
还在堆中,我们没有必要把(i, j + 1)
放入堆中。
因此,我们首先将所有(i, i + 1)
放入堆中,即 heap = [(i, i + 1) for all i]
。每次取出堆中的最小元素(i, j)
时(元素的大小为 nums[j] - nums[i]
,即距离),再把 (i, j + 1)
放入堆中。直到取出 k
个元素,就得到了第k
小的距离。
我们可以计算其时间复杂度是$O(Klogn)$的,但是最坏情况下$K = n^2$,当$n = 10000$的时候,是无法通过测试样例的。
struct pairs
{
int first,second,idx;
pairs(){}
pairs(int first,int second,int idx):first(first),second(second),idx(idx){};
bool operator< (const pairs & a) const
{
return (second - first) > (a.second - a.first);
}
};
int smallestDistancePair(vector<int>& nums, int k) {
sort(nums.begin(),nums.end());
int n = nums.size();
priority_queue<pairs> q;
for(int i = 0 ; i < n - 1 ; i ++)
q.push(pairs(nums[i],nums[i + 1],i + 1));
for(int i = 0 ; i < k - 1; i ++)
{
auto t = q.top();
q.pop();
if(t.idx < n - 1)
q.push(pairs(t.first,nums[t.idx + 1],t.idx + 1));
}
return q.top().second - q.top().first;
}
算法2
(二分查找+双指针) $O(nlogn + nlogL)$
题解2:二分查找+双指针。同样的我们首先将数组排好序。我们知道这样一个问题最终的答案肯定在[0:nums[n - 1] - nums[0]]
之间,那么我们可以通过二分查找到使得满足条件(小于等于target
的距离对大于等于k
个)的最小值就是我们的答案,那么问题就可以转化成如何快速的查找nums
数组中小于等于target
的距离对。因为数组是已经排好序的,如果nums[j] - nums[i] <= target
,那么肯定有nums[j] - nums[i + 1] <= target
。我们令j
是使得nums[j] - nums[i] <= target
最大的元素下标,那么我们可以得到j
是随着i
单调递增的,所以我们可以使用双指针在$O(n)$的时间内解决这个问题。这样总的时间复杂度被压缩到$O(nlogn + nlogL)$
class Solution {
public:
bool check(vector<int>& nums,int n,int k,int mid)
{
int cnt = 0;
for(int i = 0,j = 1; i < n - 1 ; i ++)
{
while(j < n && nums[j] - nums[i] <= mid)
j ++;
cnt += j - i - 1;
j = max(j,i + 1);
}
return cnt >= k;
}
int smallestDistancePair(vector<int>& nums, int k)
{
int n = nums.size();
sort(nums.begin(),nums.end());
int left = 0,right = nums[n - 1] - nums[0];
while(left < right)
{
int mid = (left + right) >> 1;
if(check(nums,n,k,mid)) right = mid;
else left = mid + 1;
}
return left;
}
};