algorithm - 如何从双向链表中找到第 k 个最小元素？

Question

我需要实现一个可以从双向链表中找到第 k 个最小值的函数。

我在网上搜索并了解到这个:

• quickSelect 逻辑和 k 阶统计算法对数组或向量有效，但我在这里使用链表，我没有任何大小的链表，因此很难将它们分成 5 个元素部分。

我的函数测试用例是这样的:

for(int i = 0; i < 1000; ++i)
{
    // create linked list with 1000 elements
    int kthMinimum = findKthMin(LinkedList, i);
    // validate kthMinimum answer.
}

这里的链表可以是任意顺序的，我们必须假设只是随机的。

有什么想法或建议可以高效地从双向链表中找到第 k 个最小值吗？

谢谢

Answer 1

算法

您可以通过执行以下操作来维护大小为 k 的堆:

1. 用列表的第 k 个元素填充数组。
2. 堆化数组(使用 MaxHeap)
3. 处理列表的剩余元素:
   • 如果堆顶(最大值)大于列表中的当前元素e，将其替换为e(并保持堆不变)<
   • 如果元素更大，直接忽略继续

在算法结束时，第 k 个最小的元素将位于堆的顶部。

复杂性

累加前k个元素+堆化数组:O(k)
处理列表的剩余部分 O((n-k)ln(k))。