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.
Approach #1: Brute Force.[Memory Limit Exceeded]
class Solution {
public:
int smallestDistancePair(vector<int>& nums, int k) {
int len = nums.size();
vector<int> temp;
for (int i = 0; i < len; ++i) {
for (int j = i+1; j < len; ++j) {
int sub = abs(nums[i] - nums[j]);
temp.push_back(sub);
}
}
sort(temp.begin(), temp.end());
return temp[k-1];
}
};
Approach #2: Brute Force. [Bucter Sort]
class Solution {
public:
int smallestDistancePair(vector<int>& nums, int k) {
int len = nums.size();
sort(nums.begin(), nums.end());
int N = nums.back();
vector<int> container(N+1, 0);
for (int i = 0; i < len; ++i) {
for (int j = i+1; j < len; ++j) {
++container[nums[j]-nums[i]];
}
}
for (int i = 0; i <= N; ++i) {
k -= container[i];
if (k <= 0) return i;
}
return 0;
}
};
Runtime: 580 ms, faster than 13.29% of C++ online submissions for Find K-th Smallest Pair Distance.
Approach #2: Binary Search + DP
class Solution {
public:
int smallestDistancePair(vector<int>& nums, int k) {
int len = nums.size();
sort(nums.begin(), nums.end());
int l = 0;
int r = nums.back() - nums.front();
while (l <= r) {
int count = 0;
int j = 0;
int m = l + (r - l) / 2;
for (int i = 0; i < len; ++i) {
while (j < len && nums[j] - nums[i] <= m) j++;
count += j - i - 1;
}
count >= k ? r = m - 1 : l = m + 1;
}
return l;
}
};
Runtime:
16 ms, faster than 43.93% of C++ online submissions for Find K-th Smallest Pair Distance.
we can use a constant to instead dp array.