Find K-th Smallest Pair Distance：查找数组元素中差值第K大的两个元素的差值

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:

1. 2 <= len(nums) <= 10000.
2. 0 <= nums[i] < 1000000.
3. 1 <= k <= len(nums) * (len(nums) - 1) / 2.

思路：二分查找+滑动窗口思想，很巧妙的一道题。最后二分查找注释的位置困扰了我好久。

class Solution {
   public int smallestDistancePair(int[] nums, int k) {
       Arrays.sort(nums);
       
       int l =0;
       int h =nums[nums.length-1]-nums[0];
       while(l<h){//二分查找，因为当count==k时，搜索到的m差值可能并不存在，需要继续循环判断，直到范围确定           
           int m = (l + h)/2;          
           //search
           //使用窗口思想，判断差值<=k的个数，r-l即表示[l,r]间间隔<m的个数（每确定一个窗口就新增加了（r-l+1）- 1个差值对）
           int left = 0;
           int count = 0;
           for(int right = 0;right<nums.length;right++){
               while(nums[right] - nums[left]>m){
                   left++;
               }
               count+= right-left;
           }
           /*注意，下面这种写法是错误的，因为比如l=3，r=4，m=(3+4)/2 = 3(因为是向下取整)，所以此次迭代有可能l=m后，l=3，r=4陷入死循环！
           if(count<=k){
               l = m ;
           }else{
               h = m-1;
           }
           */
           
           if(count>=k){
               h = m ;
           }else{
               l = m+1;
           }          
       }
        return l;
    }
}

复杂度：

Complexity Analysis

• Time Complexity: O(N \log{W} + N \log{N})O(NlogW+NlogN), where NN is the length of nums, and WW is equal to nums[nums.length - 1] - nums[0]. The \log WlogW factor comes from our binary search, and we do O(N)O(N) work inside our call to possible (or to calculate count in Java). The final O(N\log N)O(NlogN) factor comes from sorting.

• Space Complexity: O(1)O(1). No additional space is used except for integer variables.