Question

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

Solution 1

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)

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;
  }
};

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;
}