标签 algorithm
<分区>
Possible Duplicate:
How to find the kth largest element in an unsorted array of length n in O(n)?
我目前正坐在类(class)作业前。 任务是找到数组中第 n 个最小的元素。 (没有排序!)
我试图理解 BFPRT 算法，但据我所知，它仅在您想计算中位数而不是“第 n 个最小”元素时才有用。
我的另一个想法是通过将较小/较大的节点附加到根节点的左侧/右侧，将数组转换为树。但是我不确定这是否算作排序。 为了加快速度，我可以存储每个节点中的子节点数。
完整的作业还包括算法必须是递归的。 还有提示要考虑其他数据结构。
您如何看待我将数组转换为平衡树的想法？
还有我可能错过的任何其他选项吗？
编辑:我查看了各种类似的问题，但无法完全理解答案/将它们应用到我的特定任务中。
最佳答案
解决此问题(顺序统计问题)的传统方法让人想起快速排序。假设您正在寻找第 k 个最小元素。选择一个(随机)枢轴元素并将剩余元素分成两组(不对两组进行排序):L 包含所有小于或等于枢轴元素的元素(除了枢轴元素本身), G 包含所有大于主元的元素。 L 有多大？如果它恰好包含 k - 1 个元素，则枢轴元素必须是第 k 个最小元素，您就完成了。如果 L 包含超过 k - 1 个元素，则第 k 个最小的元素必须在 L 中；否则，它在 G 中。现在，将相同的算法应用于 L 或 G(如果您需要使用 G，则必须调整 k 因为您不再寻找 G 的第 k 个最小元素，而是整个 k 个最小的元素。k p>
该算法在预期的 O(n) 时间内运行；然而，该算法存在一个巧妙的修改，可以在最坏的情况下保证 O(n) 时间。
编辑:正如@Ishtar 指出的那样，“巧妙的修改”是 BFPRT 算法。它的核心思想是确保你永远不会选择一个坏的主元，这样两个分区 L 和 G 就不会变得太不平衡。只要能保证一个分区永远不会比另一个分区大 c 倍(对于一些任意但固定的 c)，运行时间将是 < em>O(n).
关于algorithm - 查找数组中第 n 个最小的元素，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/6072319/