[LeetCode]Find K-th Smallest Pair Distance

这道题和Find K Pairs with Smallest Sum是类似的，我们同样可以将1D转化成2D，如下图所示：

因为我们不考虑自己和自己的差值，所以我们只考虑对角线斜向上的那一半区域。这个区域的值是自下而上自左而右递增的。并且我们可以sort array并且很简单的求出最大和最小的distance，也就是说我们可以用和K Pairs一样的方法来做一道题。因为sorted的性质，我们可以看做m个长度为n的sorted list用priority queue一个一个取直到取到第k个，但是我们有类似Kth Smallest Element in Sorted Matrix的值域Binary Search的更好的方法。同样每次求出mid然后统计小于等于mid的值的数量c，如果c >= k，hi = mid; 如果c < k, lo = mid + 1。因为array的值是有规律的，我们只需要最多m + n的时间就可以求出，假设第一列有x个小于mid的数，那么第二列就一定有>= x个，我们只需要将行指针单调地向下移动即可，列指针也是单调地向右移动，所以总的时间不会超过m + n。时间复杂度T(v) = T(v / 2) + m + n，考虑m + n一般小于v, 时间复杂度O(v * log v), 代码如下：