对于leetcode 719.第k小的距离,如果不使用二分法,你会如何求解

如果不使用二分法，可以使用堆来解决这个问题。具体地，我们使用一个小根堆，初始时只包含 (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)。