求第 K 个数的问题

一道经典的题目。给一堆乱序的数,如果它们从小到大排好,求第 k 个是多少。假设排列的下标从 1 开始,而非 0 开始。

这个问题如此之简单而熟悉,可它却可以是很多现实问题的某一个子问题的抽象。它本身相关的问题其实就不少,而且还可以不断演进,成为不同复杂程度的问题。

关于这个问题的分析和演进,我们不妨从一左一右两条分支——堆排序或者快排,来分别进行。在不断演化问题的时候,会这两个分支之间跳来跳去,为了尽量清晰的考虑,我采用一种新方法——使用 【分支:堆排序】【分支:快排】 来标注。

Java 中快排用 Arrays.sort 就可以了,如果是堆排序需要用到 PriorityQueue。 用 Array[……]阅读全文

back to top