Find K-th Smallest Pair Distance

题目

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:
2 <= len(nums) <= 10000.
0 <= nums[i] < 1000000.
1 <= k <= len(nums) * (len(nums) - 1) / 2.

解题报告

理解题意

• 给定数组，让在所有的距离对中求第 k 个最小的距离，然后给出距离对的定义是 (a,b) –> a 和 b 的差值

理解例子

• {1,3,1} 数组，可能有的距离对的个数为 n * (n - 1) / 2
• 所有的距离对为：(1, 3) (1, 1) (3, 1) 他们的距离值为: 2, 0 ,2
• 因此排在第 1 位的最小的距离对为 (1,1) 结果为 0

思路

• 首先想到的就是暴力解法，我们得知道所有可能的距离对，然后计算每个对的差值，求第 k 个。
• 转念一想，其实没必要把距离对求出来，只要求出所有可能的差值就行。
• 但差值可能有好几个，模式点像桶排序，O(n)时间就可完成排序，那么就得知道需要多少个桶。
• 所以对输入数据进行排序后，最大的值，就知道了，也就知道桶的个数了。
• 每个桶里放差值的个数即可，就能知道排在第几位的桶有多少个，也就能回答问题

代码

class Solution {
public:
    int smallestDistancePair(vector<int>& nums, int k) {
        sort(nums.begin(), nums.end());
        int n = nums.back();
        const int m = nums.size();
        vector<int> freq(n+1, 0);
        for (int i = 0; i < m; i++) {
            for (int j = i+1; j < m; j++)
                freq(nums[j]-nums[i])++;
        }
        for (int i = 0; i < n; i++) {
            k -= freq[i];
            if (k <= 0) return i;
        }
        return 0;
    }
};

时间复杂度

\(\mathcal{O(n^2)}\)

空间复杂度

因此空间复杂度也为 \(\mathcal{O(max(n))}\)

优化

• 提交后通过了，但是所有的性能指标是在最后的最后，还是优化一下符合要求
• 桶排序的内存要求比较高，另外，在求所有元素对的地方耗费太多时间，那个地方也是优化点。
• 这道题目的步骤大概可以分为两个，首先的知道距离对的内容，然后就是找 k 个满足条件的距离对
• 距离对的内容，可以使用 dp 来解决，那么 dp 的状态转换方程应该怎么写呢？

思路

• 由于题目让求排在第 k 位的最小的距离对。之前的 lower_bound 是查找≥某个数的第一个位置， upper_bound 是求＞某个数的第一个位置。因此这道题应该是让查：差值，这个差值还得满足至少有 k 个差值是小于等于它的。
• 因此如果要使用折半查找的数据内容是表示 以上内容的，就可以方便的使用折半查找了。
• 假定内容是升序排列，假定 d_ij 表示 对于(i,j) 距离对且 i < j，那么 d_id = nums[j] - nums[i]
• 如果 i 位置不变的话，d_ij <= num 就等价于 nums[j] <= nums[i] + num
• 那么也就是说要去找最小的 j 保证 nums[j] > nums[i] + num
• 计数也可以使用双指针，在线性时间下完成

  • 假定两个起点 l1 < l2，满足 nums[j1] > nums[i1] + num 和 nums[j2] > nums[i2] + num —> j2 > j1