虎牙Android面试题及参考答案

给个数组，找出数组中第 k 大的数（利用快排思想 / 用小顶堆，他说可以用大顶堆？）

• 利用快排思想：快速排序的核心思想是分治和分区。在找数组中第 k 大的数时，每次选择一个基准元素，将数组分为两部分，左边部分小于基准元素，右边部分大于基准元素。如果基准元素最终的下标是 n - k（n 是数组长度），那么这个基准元素就是第 k 大的数。如果基准元素的下标小于 n - k，说明第 k 大的数在基准元素右边的部分，继续在右边部分进行分区操作；如果基准元素的下标大于 n - k，则在基准元素左边的部分继续进行分区操作。这种方法的平均时间复杂度为 ，最坏情况下时间复杂度为 ，空间复杂度为 （递归调用栈的空间）。
• 利用小顶堆：首先创建一个大小为 k 的小顶堆，将数组中的前 k 个元素放入小顶堆中。然后从第 k + 1 个元素开始遍历数组，如果当前元素大于小顶堆的堆顶元素，则将堆顶元素弹出，把当前元素插入小顶堆。遍历完整个数组后，小顶堆的堆顶元素就是数组中第 k 大的数。时间复杂度为 ，空间复杂度为 ，因为需要维护一个大小