0719. Find K-th Smallest Pair Distance ======================================================================================================================== 题目信息 -------- :题号: 0719 :难度: Hard :主题: 数组、数对距离、顺序统计 :原题: `LeetCode 0719 `_ :重点: 数对由不同下标 ``i < j`` 确定,距离为两值之差的绝对值;所有下标对的距离保留重复并按升序取第 ``k`` 个 题目重述 -------- 给定整数数组 ``nums`` 和正整数 ``k``。对每一组满足 ``0 <= i < j < nums.length`` 的下标,定义对应数对的距离为 ``abs(nums[i] - nums[j])``。 把全部 ``n * (n - 1) / 2`` 个下标对的距离按非递减顺序排列,返回其中第 ``k`` 小的距离。``k`` 从 1 开始计数;不同下标对即使得到相同距离,也要作为多个元素分别参与排名。 数组长度 ``n`` 在 ``[2, 10^4]`` 范围内,``0 <= nums[i] <= 10^6``,并且 ``1 <= k <= n * (n - 1) / 2``。 自建示例 -------- 重复距离按下标对分别计数: .. code-block:: text 输入:nums = [4,1,7,1], k = 4 输出:3 解释:六个下标对的距离排序后为 [0,3,3,3,6,6],第 4 个距离是 3。 最小数组取到数值范围两端: .. code-block:: text 输入:nums = [0,1000000], k = 1 输出:1000000 解释:数组达到最小长度 2,只存在下标对 (0,1),其距离为 1000000。唯一候选同时是第 1 小距离,两个元素也分别取到允许的最小值和最大值。