0719-找出第 K 小的数对距离

Raphael Liu Lv10
  2023-09-13 00:47:26 2023-09-13 00:47:26 Created   2023-09-13 16:06:29 2023-09-13 16:06:29 Updated    

数对 (a,b) 由整数 a 和 b 组成，其数对距离定义为 a 和 b 的绝对差值。

给你一个整数数组 nums 和一个整数 k ，数对由 nums[i] 和 nums[j] 组成且满足 0 <= i < j < nums.length 。返回 所有数对距离中 第 k 小的数对距离。

示例 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 <= 104
  • 0 <= nums[i] <= 106
  • 1 <= k <= n * (n - 1) / 2

方法一：排序 + 二分查找

先将数组 nums 从小到大进行排序。因为第 k 小的数对距离必然在区间 [0, \max (\textit{nums}) - \min(\textit{nums})] 内，令 left} = 0，right} = \max (\textit{nums}) - \min(\textit{nums})，我们在区间 [\textit{left}, \textit{right}] 上进行二分。

对于当前搜索的距离 mid，计算所有距离小于等于 mid 的数对数目 cnt，如果 cnt} \ge k，那么 right} = \textit{mid} - 1，否则 left} = \textit{mid} + 1。当 left} \gt \textit{right 时，终止搜索，那么第 k 小的数对距离为 left。

给定距离 mid，计算所有距离小于等于 mid 的数对数目 cnt 可以使用二分查找：枚举所有数对的右端点 j，二分查找大于等于 nums}[j] - \textit{mid 的最小值的下标 i，那么右端点为 j 且距离小于等于 mid 的数对数目为 j - i，计算这些数目之和。

[sol1-Python3]
1
2
3
4
5
6
7
8
9
10
11
class Solution:
    def smallestDistancePair(self, nums: List[int], k: int) -> int:
        def count(mid: int) -> int:
            cnt = 0
            for j, num in enumerate(nums):
                i = bisect_left(nums, num - mid, 0, j)
                cnt += j - i
            return cnt

        nums.sort()
        return bisect_left(range(nums[-1] - nums[0]), k, key=count)
[sol1-C++]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
    int smallestDistancePair(vector<int>& nums, int k) {
        sort(nums.begin(), nums.end());
        int n = nums.size(), left = 0, right = nums.back() - nums.front();
        while (left <= right) {
            int mid = (left + right) / 2;
            int cnt = 0;
            for (int j = 0; j < n; j++) {
                int i = lower_bound(nums.begin(), nums.begin() + j, nums[j] - mid) - nums.begin();
                cnt += j - i;
            }
            if (cnt >= k) {
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }
        return left;
    }
};
[sol1-Java]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
class Solution {
    public int smallestDistancePair(int[] nums, int k) {
        Arrays.sort(nums);
        int n = nums.length, left = 0, right = nums[n - 1] - nums[0];
        while (left <= right) {
            int mid = (left + right) / 2;
            int cnt = 0;
            for (int j = 0; j < n; j++) {
                int i = binarySearch(nums, j, nums[j] - mid);
                cnt += j - i;
            }
            if (cnt >= k) {
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }
        return left;
    }

    public int binarySearch(int[] nums, int end, int target) {
        int left = 0, right = end;
        while (left < right) {
            int mid = (left + right) / 2;
            if (nums[mid] < target) {
                left = mid + 1;
            } else {
                right = mid;
            }
        }
        return left;
    }
}
[sol1-C#]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
public class Solution {
    public int SmallestDistancePair(int[] nums, int k) {
        Array.Sort(nums);
        int n = nums.Length, left = 0, right = nums[n - 1] - nums[0];
        while (left <= right) {
            int mid = (left + right) / 2;
            int cnt = 0;
            for (int j = 0; j < n; j++) {
                int i = BinarySearch(nums, j, nums[j] - mid);
                cnt += j - i;
            }
            if (cnt >= k) {
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }
        return left;
    }

    public int BinarySearch(int[] nums, int end, int target) {
        int left = 0, right = end;
        while (left < right) {
            int mid = (left + right) / 2;
            if (nums[mid] < target) {
                left = mid + 1;
            } else {
                right = mid;
            }
        }
        return left;
    }
}
[sol1-C]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
int cmp(const void* pa, const void* pb) {
    return *(int *)pa - *(int *)pb;
}

int binarySearch(int* nums, int end, int target) {
    int left = 0, right = end - 1;
    while (left <= right) {
        int mid = (left + right) / 2;
        if (nums[mid] < target) {
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }
    return left;
}

int smallestDistancePair(int* nums, int numsSize, int k) {
    qsort(nums, numsSize, sizeof(int), cmp);
    int left = 0, right = nums[numsSize - 1] - nums[0];
    while (left <= right) {
        int mid = (left + right) / 2;
        int cnt = 0;
        for (int j = 0; j < numsSize; j++) {
            int i = binarySearch(nums, j, nums[j] - mid);
            cnt += j - i;
        }
        if (cnt >= k) {
            right = mid - 1;
        } else {
            left = mid + 1;
        }
    }
    return left;
}
[sol1-Golang]
1
2
3
4
5
6
7
8
9
10
11
func smallestDistancePair(nums []int, k int) int {
    sort.Ints(nums)
    return sort.Search(nums[len(nums)-1]-nums[0], func(mid int) bool {
        cnt := 0
        for j, num := range nums {
            i := sort.SearchInts(nums[:j], num-mid)
            cnt += j - i
        }
        return cnt >= k
    })
}
[sol1-JavaScript]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
var smallestDistancePair = function(nums, k) {
    nums.sort((a, b) => a - b);
    let n = nums.length, left = 0, right = nums[n - 1] - nums[0];
    while (left <= right) {
        const mid = Math.floor((left + right) / 2);
        let cnt = 0;
        for (let j = 0; j < n; j++) {
            const i = binarySearch(nums, j, nums[j] - mid);
            cnt += j - i;
        }
        if (cnt >= k) {
            right = mid - 1;
        } else {
            left = mid + 1;
        }
    }
    return left;
};

const binarySearch = (nums, end, target) => {
    let left = 0, right = end;
    while (left < right) {
        const mid = Math.floor((left + right) / 2);
        if (nums[mid] < target) {
            left = mid + 1;
        } else {
            right = mid;
        }
    }
    return left;
}

复杂度分析

  • 时间复杂度：O(n \log n \times \log D)，其中 n 是数组 nums 的长度，D = \max(\textit{nums}) - \min(\textit{nums})。外层二分查找需要 O(\log D)，内层二分查找需要 O(n \log n)。

  • 空间复杂度：O(\log n)。排序的平均空间复杂度为 O(\log n)。

方法二：排序 + 二分查找 + 双指针

给定距离 mid，计算所有距离小于等于 mid 的数对数目 cnt 可以使用双指针：初始左端点 i = 0，我们从小到大枚举所有数对的右端点 j，移动左端点直到 nums}[j] - \textit{nums}[i] \le \textit{mid，那么右端点为 j 且距离小于等于 mid 的数对数目为 j - i，计算这些数目之和。

[sol2-Python3]
1
2
3
4
5
6
7
8
9
10
11
12
class Solution:
    def smallestDistancePair(self, nums: List[int], k: int) -> int:
        def count(mid: int) -> int:
            cnt = i = 0
            for j, num in enumerate(nums):
                while num - nums[i] > mid:
                    i += 1
                cnt += j - i
            return cnt

        nums.sort()
        return bisect_left(range(nums[-1] - nums[0]), k, key=count)
[sol2-C++]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
public:
    int smallestDistancePair(vector<int>& nums, int k) {
        sort(nums.begin(), nums.end());
        int n = nums.size(), left = 0, right = nums.back() - nums.front();
        while (left <= right) {
            int mid = (left + right) / 2;
            int cnt = 0;
            for (int i = 0, j = 0; j < n; j++) {
                while (nums[j] - nums[i] > mid) {
                    i++;
                }
                cnt += j - i;
            }
            if (cnt >= k) {
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }
        return left;
    }
};
[sol2-Java]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
    public int smallestDistancePair(int[] nums, int k) {
        Arrays.sort(nums);
        int n = nums.length, left = 0, right = nums[n - 1] - nums[0];
        while (left <= right) {
            int mid = (left + right) / 2;
            int cnt = 0;
            for (int i = 0, j = 0; j < n; j++) {
                while (nums[j] - nums[i] > mid) {
                    i++;
                }
                cnt += j - i;
            }
            if (cnt >= k) {
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }
        return left;
    }
}
[sol2-C#]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
public class Solution {
    public int SmallestDistancePair(int[] nums, int k) {
        Array.Sort(nums);
        int n = nums.Length, left = 0, right = nums[n - 1] - nums[0];
        while (left <= right) {
            int mid = (left + right) / 2;
            int cnt = 0;
            for (int i = 0, j = 0; j < n; j++) {
                while (nums[j] - nums[i] > mid) {
                    i++;
                }
                cnt += j - i;
            }
            if (cnt >= k) {
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }
        return left;
    }
}
[sol2-C]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
int cmp(const void* pa, const void* pb) {
    return *(int *)pa - *(int *)pb;
}

int smallestDistancePair(int* nums, int numsSize, int k) {
    qsort(nums, numsSize, sizeof(int), cmp);
    int left = 0, right = nums[numsSize - 1] - nums[0];
    while (left <= right) {
        int mid = (left + right) / 2;
        int cnt = 0;
        for (int i = 0, j = 0; j < numsSize; j++) {
            while (nums[j] - nums[i] > mid) {
                i++;
            }
            cnt += j - i;
        }
        if (cnt >= k) {
            right = mid - 1;
        } else {
            left = mid + 1;
        }
    }
    return left;
}
[sol2-Golang]
1
2
3
4
5
6
7
8
9
10
11
12
13
func smallestDistancePair(nums []int, k int) int {
    sort.Ints(nums)
    return sort.Search(nums[len(nums)-1]-nums[0], func(mid int) bool {
        cnt, i := 0, 0
        for j, num := range nums {
            for num-nums[i] > mid {
                i++
            }
            cnt += j - i
        }
        return cnt >= k
    })
}
[sol2-JavaScript]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
var smallestDistancePair = function(nums, k) {
    nums.sort((a, b) => a - b);
    let n = nums.length, left = 0, right = nums[n - 1] - nums[0];
    while (left <= right) {
        const mid = Math.floor((left + right) / 2);
        let cnt = 0;
        for (let i = 0, j = 0; j < n; j++) {
            while (nums[j] - nums[i] > mid) {
                i++;
            }
            cnt += j - i;
        }
        if (cnt >= k) {
            right = mid - 1;
        } else {
            left = mid + 1;
        }
    }
    return left;
}

复杂度分析

  • 时间复杂度：O(n \times (\log n + \log D))，其中 n 是数组 nums 的长度，D = \max(\textit{nums}) - \min(\textit{nums})。外层二分查找需要 O(\log D)，内层双指针需要 O(n)，排序的平均时间复杂度为 O(n \log n)。

  • 空间复杂度：O(\log n)。排序的平均空间复杂度为 O(\log n)。

 Comments
On this page
0719-找出第 K 小的数对距离