T215_findKthLargest

215. 数组中的第K个最大元素

题目描述

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

示例:

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

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

思路介绍

方法一 数组法

基本介绍

1. 考虑到 需要找到 第 k 大 的 数，所以可以将前 k 大 的数 都保存到 一个 数组中

思路

1. 定义 一个 长度为 k+1 的数组 res_list，用于保存前 k+1 个 数；
2. 遍历数组，然后比较当前元素 num 和 res_list 中 元素 间的大小（从后到前比较）：
   1. 若 大于，则将 res_list 后移，然后插入 num

复杂度计算

时间复杂度：O(n*(k+1))

空间复杂度：O(k+1)

方法二 堆排序法

基本介绍

1. 利用堆 每一次 都能 找到 当前 最大的数，所以只要 进行 k 次 堆排序 即可找到 第 k 大 的数

思路

1. 编写堆排序算法；
2. 进行 k 次 堆排序；

复杂度计算

时间复杂度：O(nlogK+n) 空间复杂度：O(1)

方法三 基于 内部库 的 堆排序法

基本介绍

和方法二类似

方法四 快排

基本介绍

1. 对 数组进行快排，然后 取位置 k 元素 即可

复杂度计算

时间复杂度：O(nlogn)

空间复杂度：O(1)