Hard

题目描述

数对 (a, b) 的距离定义为 a 和 b 之间的绝对差值。

给定一个整数数组 nums 和一个整数 k，返回所有数对 nums[i] 和 nums[j] 中第 k 小的距离，其中 0 <= i < j < nums.length。

示例 1：

输入：nums = [1,3,1], k = 1
输出：0
解释：所有数对如下：
(1,3) -> 2
(1,1) -> 0
(3,1) -> 2
第1小的距离数对是 (1,1)，距离为 0。

示例 2：

输入：nums = [1,1,1], k = 2
输出：0

示例 3：

输入：nums = [1,6,1], k = 3
输出：5

提示：

  • n == nums.length
  • 2 <= n <= 10^4
  • 0 <= nums[i] <= 10^6
  • 1 <= k <= n * (n - 1) / 2

解题思路

解题思路

这道题要求找到第 k 小的数对距离，直接枚举所有数对会导致时间复杂度过高。我们可以使用二分搜索的思想来解决。

核心思路

  1. 二分搜索答案：距离的范围在 [0, max(nums) - min(nums)] 之间，我们可以在这个范围内二分搜索目标距离值
  2. 验证函数：对于每个候选距离 mid，统计有多少个数对的距离 ≤ mid
  3. 双指针优化：为了高效统计距离 ≤ mid 的数对数量，先对数组排序，然后使用双指针技巧

具体步骤

  1. 对数组进行排序，使得相近的数字聚集在一起
  2. 使用二分搜索在可能的距离范围内查找答案
  3. 对于每个候选距离 mid，使用双指针统计距离 ≤ mid 的数对数量：
    • 固定左指针 i，移动右指针 j
    • 当 nums[j] - nums[i] <= mid 时，说明从 i 到 j 的所有数对距离都 ≤ mid
    • 累加数对数量：j - i

时间复杂度优化

通过排序 + 双指针，我们可以在 O(n) 时间内统计距离 ≤ mid 的数对数量，整体复杂度为 O(n log(max_distance))。

代码实现

class Solution {
public:
    int smallestDistancePair(vector<int>& nums, int k) {
        sort(nums.begin(), nums.end());
        
        int left = 0, right = nums.back() - nums[0];
        
        while (left < right) {
            int mid = left + (right - left) / 2;
            int count = countPairs(nums, mid);
            
            if (count < k) {
                left = mid + 1;
            } else {
                right = mid;
            }
        }
        
        return left;
    }
    
private:
    int countPairs(const vector<int>& nums, int maxDistance) {
        int count = 0;
        int j = 0;
        
        for (int i = 0; i < nums.size(); i++) {
            while (j < nums.size() && nums[j] - nums[i] <= maxDistance) {
                j++;
            }
            count += j - i - 1;
        }
        
        return count;
    }
};

class Solution:
    def smallestDistancePair(self, nums: List[int], k: int) -> int:
        nums.sort()
        
        def countPairs(maxDistance):
            count = 0
            j = 0
            for i in range(len(nums)):
                while j < len(nums) and nums[j] - nums[i] <= maxDistance:
                    j += 1
                count += j - i - 1
            return count
        
        left, right = 0, nums[-1] - nums[0]
        
        while left < right:
            mid = (left + right) // 2
            if countPairs(mid) < k:
                left = mid + 1
            else:
                right = mid
                
        return left

public class Solution {
    public int SmallestDistancePair(int[] nums, int k) {
        Array.Sort(nums);
        
        int left = 0, right = nums[nums.Length - 1] - nums[0];
        
        while (left < right) {
            int mid = left + (right - left) / 2;
            int count = CountPairs(nums, mid);
            
            if (count < k) {
                left = mid + 1;
            } else {
                right = mid;
            }
        }
        
        return left;
    }
    
    private int CountPairs(int[] nums, int maxDistance) {
        int count = 0;
        int j = 0;
        
        for (int i = 0; i < nums.Length; i++) {
            while (j < nums.Length && nums[j] - nums[i] <= maxDistance) {
                j++;
            }
            count += j - i - 1;
        }
        
        return count;
    }
}

var smallestDistancePair = function(nums, k) {
    nums.sort((a, b) => a - b);
    
    const countPairs = (maxDistance) => {
        let count = 0;
        let j = 0;
        for (let i = 0; i < nums.length; i++) {
            while (j < nums.length && nums[j] - nums[i] <= maxDistance) {
                j++;
            }
            count += j - i - 1;
        }
        return count;
    };
    
    let left = 0, right = nums[nums.length - 1] - nums[0];
    
    while (left < right) {
        const mid = Math.floor((left + right) / 2);
        if (countPairs(mid) < k) {
            left = mid + 1;
        } else {
            right = mid;
        }
    }
    
    return left;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度说明
时间复杂度O(n log n + n log(max_distance))排序 O(n log n)，二分搜索 O(log(max_distance)) × 统计函数 O(n)
空间复杂度O(1)只使用常数额外空间，不考虑排序的空间开销

相关题目