719 Find K-th Smallest Pair Distance

1. Question

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:
1
Input:
2
nums = [1,3,1]
3
k = 1
4
Output: 0
5
Explanation:
6
Here are all the pairs:
7
(1,3) -> 2
8
(1,1) -> 0
9
(3,1) -> 2
10
Then the 1st smallest distance pair is (1,1), and its distance is 0.
Copied!
Note:
  1. 1.
    2 <= len(nums) <= 10000.
  2. 2.
    0 <= nums[i] < 1000000.
  3. 3.
    1 <= k <= len(nums) * (len(nums) - 1) / 2.

2. Implementation

(1) Binary Search
思路: 这题的居然思路和 Kth Smallest Element in a Sorted Matrix一样,不同的是searchAndCount的逻辑不同,实在没想到。对于这种求第K小/大的题目中,如果其中包含某些带有顺序属性的性质,我们可以用二分法求出结果
1
class Solution {
2
public int smallestDistancePair(int[] nums, int k) {
3
Arrays.sort(nums);
4
5
int start = 0, end = nums[nums.length - 1] - nums[0], mid = 0;
6
int count = 0;
7
8
while (start < end) {
9
mid = start + (end - start) / 2;
10
11
count = searchAndCount(mid, nums);
12
13
if (count < k) {
14
start = mid + 1;
15
}
16
else {
17
end = mid;
18
}
19
}
20
return start;
21
}
22
23
public int searchAndCount(int target, int[] nums) {
24
int count = 0;
25
int start = 0;
26
27
for (int end = 0; end < nums.length; end++) {
28
while (nums[end] - nums[start] > target) {
29
++start;
30
}
31
count += end - start;
32
}
33
return count;
34
}
35
}
Copied!
(2) Heap (TLE)
1
class Solution {
2
public int smallestDistancePair(int[] nums, int k) {
3
Arrays.sort(nums);
4
PriorityQueue<PairDiff> minHeap = new PriorityQueue<>();
5
6
for (int i = 1; i < nums.length; i++) {
7
minHeap.add(new PairDiff(i - 1, i, Math.abs(nums[i - 1] - nums[i])));
8
}
9
10
int res = 0;
11
12
for (int i = 0; i < k; i++) {
13
PairDiff curDiff = minHeap.remove();
14
15
int index1 = curDiff.index1;
16
int index2 = curDiff.index2;
17
res = curDiff.diff;
18
19
if (index2 + 1 < nums.length) {
20
minHeap.add(new PairDiff(index1, index2 + 1, Math.abs(nums[index1] - nums[index2 + 1])));
21
}
22
}
23
return res;
24
}
25
26
class PairDiff implements Comparable<PairDiff> {
27
int index1, index2, diff;
28
29
public PairDiff(int index1, int index2, int diff) {
30
this.index1 = index1;
31
this.index2 = index2;
32
this.diff = diff;
33
}
34
35
public int compareTo(PairDiff that) {
36
return this.diff - that.diff;
37
}
38
}
39
}
Copied!

3. Time & Space Complexity

Binary Search: 时间复杂度O(nlogn + (n^2) *logD), 其中D是数组中最大的diff的值,因为我们是在【0, maxDiff】这个space里进行二分搜索的
Heap: 时间复杂度O(nlogn + klogn), 空间复杂度O(n)