题目大意：给你一个数组，返回所有数对中，绝对值差第k小的值。
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:
|
1 2 3 4 5 6 7 8 9 10 |
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.
Idea
Bucket sort
Binary search / dp
Solution
C++ / binary search
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 |
// Author: Huahua // Runtime: 9 ms class Solution { public: int smallestDistancePair(vector<int>& nums, int k) { std::sort(nums.begin(), nums.end()); int n = nums.size(); int l = 0; int r = nums.back() - nums.front(); while (l <= r) { int cnt = 0; int j = 0; int m = l + (r - l) / 2; for (int i = 0; i < n; ++i) { while (j < n && nums[j] - nums[i] <= m) ++j; cnt += j - i - 1; } cnt >= k ? r = m - 1 : l = m + 1; } return l; } }; |
C++ / bucket sort w/ vector O(n^2)
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 |
// Author: Huahua // Runtime: 549 ms class Solution { public: int smallestDistancePair(vector<int>& nums, int k) { std::sort(nums.begin(), nums.end()); const int N = nums.back(); vector<int> count(N + 1, 0); const int n = nums.size(); for (int i = 0; i < n; ++i) for (int j = i + 1; j < n; ++j) ++count[nums[j] - nums[i]]; for (int i = 0; i <= N; ++i) { k -= count[i]; if (k <= 0) return i; } return 0; } }; |
Related Problems: