对于leetcode 719.第k小的距离,如果不使用二分法,你会如何求解
时间: 2023-05-29 10:02:53 浏览: 237
如果不使用二分法,可以使用堆来解决这个问题。具体地,我们使用一个小根堆,初始时只包含 (A[i], i) 和 (A[j], j),其中 i < j,然后我们执行 kk 次以下操作:弹出当前堆顶 (x, i),然后将 (A[j], j) 加入堆中,其中 j > i。在弹出堆顶时,我们统计 (x - A[i]),并将 (A[i+1], i+1) 加入堆中。这里的思想是类似于归并排序的,我们维护了两个指针分别指向 A 的两个元素,每次只取其中较小的一个,更新指针即可。堆中的元素在指针的另一侧,每次加入一个新元素时根据指针大小关系加入不同的位置即可。时间复杂度为 O(klogk)。
阅读全文
相关推荐













