求第 K 个数的问题

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

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

看到这个问题,脑海里的第一反应是一左一右红蓝两条分支——堆排序或者快排。Java 中快排用 Arrays.sort 就可以了,如果是堆排序需要用到 PriorityQueue。 用 Arrays.sort 写起来最简单(这里的参数校验都省掉了):

public int getKth(int[] nums, int k) {
    int[

[……]阅读全文

back to top