Welcome to Subscribe On Youtube

719. Find K-th Smallest Pair Distance

Description

The distance of a pair of integers a and b is defined as the absolute difference between a and b.

Given an integer array nums and an integer k, return the kth smallest distance among all the pairs nums[i] and nums[j] where 0 <= i < j < nums.length.

 

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.

Example 2:

Input: nums = [1,1,1], k = 2
Output: 0

Example 3:

Input: nums = [1,6,1], k = 3
Output: 5

 

Constraints:

  • n == nums.length
  • 2 <= n <= 104
  • 0 <= nums[i] <= 106
  • 1 <= k <= n * (n - 1) / 2

Solutions

  • class Solution {
        public int smallestDistancePair(int[] nums, int k) {
            Arrays.sort(nums);
            int left = 0, right = nums[nums.length - 1] - nums[0];
            while (left < right) {
                int mid = (left + right) >> 1;
                if (count(mid, nums) >= k) {
                    right = mid;
                } else {
                    left = mid + 1;
                }
            }
            return left;
        }
    
        private int count(int dist, int[] nums) {
            int cnt = 0;
            for (int i = 0; i < nums.length; ++i) {
                int left = 0, right = i;
                while (left < right) {
                    int mid = (left + right) >> 1;
                    int target = nums[i] - dist;
                    if (nums[mid] >= target) {
                        right = mid;
                    } else {
                        left = mid + 1;
                    }
                }
                cnt += i - left;
            }
            return cnt;
        }
    }
    
  • class Solution {
    public:
        int smallestDistancePair(vector<int>& nums, int k) {
            sort(nums.begin(), nums.end());
            int left = 0, right = nums.back() - nums.front();
            while (left < right) {
                int mid = (left + right) >> 1;
                if (count(mid, k, nums) >= k)
                    right = mid;
                else
                    left = mid + 1;
            }
            return left;
        }
    
        int count(int dist, int k, vector<int>& nums) {
            int cnt = 0;
            for (int i = 0; i < nums.size(); ++i) {
                int target = nums[i] - dist;
                int j = lower_bound(nums.begin(), nums.end(), target) - nums.begin();
                cnt += i - j;
            }
            return cnt;
        }
    };
    
  • class Solution:
        def smallestDistancePair(self, nums: List[int], k: int) -> int:
            def count(dist):
                cnt = 0
                for i, b in enumerate(nums):
                    a = b - dist
                    j = bisect_left(nums, a, 0, i)
                    cnt += i - j
                return cnt
    
            nums.sort()
            return bisect_left(range(nums[-1] - nums[0]), k, key=count)
    
    
  • func smallestDistancePair(nums []int, k int) int {
    	sort.Ints(nums)
    	n := len(nums)
    	left, right := 0, nums[n-1]-nums[0]
    	count := func(dist int) int {
    		cnt := 0
    		for i, v := range nums {
    			target := v - dist
    			left, right := 0, i
    			for left < right {
    				mid := (left + right) >> 1
    				if nums[mid] >= target {
    					right = mid
    				} else {
    					left = mid + 1
    				}
    			}
    			cnt += i - left
    		}
    		return cnt
    	}
    	for left < right {
    		mid := (left + right) >> 1
    		if count(mid) >= k {
    			right = mid
    		} else {
    			left = mid + 1
    		}
    	}
    	return left
    }
    
  • function smallestDistancePair(nums: number[], k: number): number {
        nums.sort((a, b) => a - b);
        const n = nums.length;
        let left = 0,
            right = nums[n - 1] - nums[0];
        while (left < right) {
            let mid = (left + right) >> 1;
            let count = 0,
                i = 0;
            for (let j = 0; j < n; j++) {
                // 索引[i, j]距离nums[j]的距离<=mid
                while (nums[j] - nums[i] > mid) {
                    i++;
                }
                count += j - i;
            }
            if (count >= k) {
                right = mid;
            } else {
                left = mid + 1;
            }
        }
        return left;
    }
    
    
  • /**
     * @param {number[]} nums
     * @param {number} k
     * @return {number}
     */
    function smallestDistancePair(nums, k) {
        nums.sort((a, b) => a - b);
        const n = nums.length;
        let left = 0,
            right = nums[n - 1] - nums[0];
    
        while (left < right) {
            const mid = (left + right) >> 1;
            let count = 0,
                i = 0;
    
            for (let j = 0; j < n; j++) {
                while (nums[j] - nums[i] > mid) {
                    i++;
                }
                count += j - i;
            }
    
            if (count >= k) {
                right = mid;
            } else {
                left = mid + 1;
            }
        }
    
        return left;
    }
    
    

All Problems

All Solutions