题目

在未排序的数组中找到第 k 个最大的元素。请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。

示例 1:

1
2

输入: [3,2,1,5,6,4] 和 k = 2
输出: 5

示例 2:

1
2

输入: [3,2,3,1,2,4,5,5,6] 和 k = 4
输出: 4

说明:

你可以假设 k 总是有效的，且 1 ≤ k ≤ 数组的长度。

题解

这道题的直接思路是排序，但排序并不是最优的，在排序的基础上可以对算法进行优化，从而使得复杂度更低。由于自己已经好久没有自实现过排序算法，基本上已经忘完，因此也打算趁这个机会温习下排序相关的算法。

快排

首先尝试使用快排解决，快排算法的说明参考文章白话经典算法系列之六 快速排序 快速搞定。

快排的主要思想就是 挖坑 + 分治，以题目中给的例子作为说明。

0 1 2 3 4 5
3 2 1 5 6 4

首先我们将v[0]中的3拿出来，存到tmp变量中。这样我们就可以认为v[0]处留下了一个坑，如下图。

0 1 2 3 4 5
？ 2 1 5 6 4

那么我们需要填坑。该怎么填呢？我们从数组的最后往前遍历，如果某个元素小于tmp，那么就填到坑里。

显然，直到v[2]时，我们才找到了值1是小于tmp的，那么我们将其填到v[0]中，对应的结构如下：

0 1 2 3 4 5
1 2 ? 5 6 4

这个时候，我们再从v[0]的右边开始往后找，找比tmp大的元素，填到v[2]的坑中，在这里我们发现v[1]是小于tmp的，因此不用填坑，同时这个时候我们已经走到了中间，那么我们把tmp填到v[2]中，结构如下：

0 1 2 3 4 5
1 2 3 5 6 4

接下来我们对v[0]-v[1]和v[3]-v[5]这两个区段做递归的填坑操作。在v[0]-v[1]这个区段中，我们人眼看到他们是已经有序的了，所以这里不再说明，继续以v[3]-v[5]区段来说。

0 1 2 3 4 5
1 2 3 5 6 4

我们取v[3]到tmp中，留下一个坑，结构如下：

0 1 2 3 4 5
1 2 3 ? 6 4

这个时候我们依旧从后往前找比tmp(5)小的元素填到坑里，这里我们找到了4，填进去，结构如下，之后留下一个新的坑。

0 1 2 3 4 5
1 2 3 4 6 ?

之后我们再从v[4]往后找比tmp(5)大的元素，这里我们找到了v[4]，即6，把它填到坑里，结构如下：

0 1 2 3 4 5
1 2 3 4 ？ 6

最后没有其他元素了，我们把tmp填到最后留下的坑里，结构如下：

0 1 2 3 4 5
1 2 3 4 5 6

接下来再往下递归，不过这个时候只剩v[3]和v[5]这两个单独的元素了，已经到底了，所以就可以结束递归了。这个时候，我们看到整个数组是已经有序的了。

按照以上的逻辑，实现快排代码如下，在实现过程中注意对边界的处理。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22

void quick_sort(vector<int> &nums, int l, int r) {
    if (l < r) {
        int i = l;
        int j = r;
        int tmp = nums[l];
        while (i < j) {
            while (i < j && nums[j] > tmp)
                j--;
            if (i < j)
                nums[i++] = nums[j];

            while (i < j && nums[i] < tmp)
                i++;
            if (i < j)
                nums[j--] = nums[i];
        }

        nums[i] = tmp;
        quick_sort(nums, l, i - 1);
        quick_sort(nums, i + 1, r);
    }
}

堆排

所谓的堆是一个完全二叉树，且满足父节点总是大于（小于）子节点的性质。

首先我们看数组{3, 2, 1, 5, 6, 4}，它对应的堆的结构如下图（这个时候还不能称之为堆，因为不满足父节点总是大于（小于）子节点的性质）。在数组中，如果我们当前值的index是i，那么它的左子节点的index是2 * i + 1，而其右子节点的index是2 * i + 2。以数值3为例，它的index是0，那么其左子节点的index是2 * 0 + 1，即1，对应数值2。而其右子节点的index是2 * 0 + 2，即2，对应数值1。

堆排序算法中，主要有2个步骤，

  1. 首先将数组堆化，即让数组满足堆的性质（父节点总是大于（小于）子节点）。
  2. 将堆的顶点与末尾元素交换，之后对除末尾元素外剩下的元素继续重复该步骤，直到待堆化的元素数量为0.

下面我们用图示详细的说明上面的过程，首先对数组进行堆化，这里我们让结果为升序，既然是升序，那么堆应该为大顶堆，根据上面的步骤很容易想到原因。我们要让根节点与最后一个元素交换位置，那么根节点显然应该为最大的节点，那自然是大顶堆。

堆化过程首先从最后一个非叶节点开始，这里是值1，将其与其子节点比较，显然其小于4，那么将他们两个交换位置，交换后结果如下。

之后往前到上一个非叶节点，即值2，同样将其与其节点比较，其最大的子节点是6，大于2，将他们交换位置，交换后结果如下。

再往前对根节点进行该操作，3显然小于6，将他们交换位置，交换后结果如下。

交换后，虽然根节点是最大的值，但交换后的3并不大于它的子节点，需要重新对其调整，将3与5交换位置，交换后结果如下。

至此，数组已经堆化完成，这已经是个大顶堆了，接下来我们将开始进行步骤2，将根节点换到最后，之后重复堆化过程。首先我们将根节点6与末尾节点1交换位置，交换后结果如下。

接下来对剩下的元素继续进行堆化过程，抛开6，最后一个非叶节点是5，满足条件，之后再看根节点1，小于5，与5交换，结果如下。

交换后节点1与其子节点不满足堆的性质，将1与最大的3交换，交换后结果如下。

这个时候堆化完成，继续将根节点5与最后一个元素2交换位置，交换后结果如下。

继续按照上面的流程操作，细节就不再画图了，直到所有的元素按照升序排列，最终的结构如下。

该堆对应的数组为{1, 2, 3, 4, 5, 6}，排序完成。

按照上面的逻辑，我们实现代码如下。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

void adjust(int *data, int i, int count) {
    int tmp = data[i];
    for (int largest = i * 2 + 1; largest < count; largest = largest * 2 + 1) {
        if (largest != count - 1 && data[largest + 1] > data[largest])
            largest++;

        if (data[largest] > tmp) {
            data[i] = data[largest];
            i = largest;
        }
        else
            break;
    }

    data[i] = tmp;
}

void HeapSort(int *data, int count) {
    for (int i = count / 2 - 1; i >= 0; i--) {
        adjust(data, i, count);
    }

    for (int i = count - 1; i > 0; i--) {
        int tmp = data[0];
        data[0] = data[i];
        data[i] = tmp;

        adjust(data, 0, i);
    }
}

解答

在了解了快排和堆排这两种排序算法周，就可以来解决这个问题了。我们可以直接将整个数组排好序，之后拿到结果，但这道题要的是第K大的数，而堆排刚好是每次会选择一个较大的元素排到末尾，那么我们在实际的循环中，压根不需要将整个数组排好序，只需要排到第N个数就行了。

对应的实现如下：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

void adjust(vector<int>& data, int i, int count) {
    int tmp = data[i];
    for (int largest = i * 2 + 1; largest < count; largest = largest * 2 + 1) {
        if (largest != count - 1 && data[largest + 1] > data[largest])
            largest++;

        if (data[largest] > tmp) {
            data[i] = data[largest];
            i = largest;
        }
        else
            break;
    }

    data[i] = tmp;
}

void HeapSort(vector<int>& data, int count, int k) {
    for (int i = count / 2 - 1; i >= 0; i--) {
        adjust(data, i, count);
    }

    for (int i = count - 1, j = 1; i > 0; i--, j++) {
        int tmp = data[0];
        data[0] = data[i];
        data[i] = tmp;

        if (j == k)
            break;

        adjust(data, 0, i);
    }
}

参考讨论，发现更多的思路是这样的，定义一个小顶堆，我们向里面添加元素，在添加时会对其中的元素进行排序。当元素超过k个时，把顶部的元素移出来，当全部的元素都添加完毕后，顶部的元素就是我们要的第K大的元素。

参考文章

https://songlee24.github.io/2014/04/02/heap-sort-implementation/

https://zh.wikipedia.org/wiki/%E5%A0%86%E6%8E%92%E5%BA%8F

https://www.cnblogs.com/chengxiao/p/6129630.html