[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), 代码如下：

	class Solution {
	public:
	int smallestDistancePair(vector<int>& nums, int k) {
	sort(nums.begin(), nums.end());
	int len = nums.size(), lo = INT_MAX, hi = nums[len - 1] - nums[0];
	if (len < 2)return -1;
	for (int i = 1; i < len; ++i)
	lo = min(lo, nums[i] - nums[i - 1]);
	while (lo < hi)
	{
	int mid = lo + (hi - lo) / 2, c = count(nums, mid);
	if (c >= k)hi = mid;
	else lo = mid + 1;
	}
	return lo;
	}
	private:
	int count(vector<int>& nums, int k) {
	int n = nums.size(), i = 0, res = 0;
	for (int j = 1; j < n; ++j)
	{
	while (i < j && nums[j] - nums[i] > k)++i;
	res += (j - i);
	}
	return res;
	}
	};

view raw Find K-th Smallest Pair Distance.cpp hosted with ❤ by GitHub