# LeetCode 215. Kth Largest Element in an Array

用户头像
liu_liu
关注
发布于: 2020 年 06 月 01 日
# LeetCode 215. Kth Largest Element in an Array

@(LeetCode)

问题描述



找出数组中第 k 个最大的数。注意是数组排序后第 k 大的数,而不是去重后的第 k 大的数。



栗 1:

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

解释:
排序后:[1,2,3,4,5,6],倒数第 2 个数为 5。



栗 2:

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

解释:
排序后:[1,2,2,3,3,4,5,5,6],倒数第 4 个数为 4。



注意:

  • 假定 k 一定有效,范围是 1 ≤ k ≤ array's length



想看英文原文的戳这里



解题思路



首先来说明一下第 k 大的数定义,即将数组从小到大排序后,从它开始到数组末尾,总共有 k 个数。



解法 1



最容易想到的思路:将数组从小到大排序后,取倒数第 k 个数。



但显然,这道题考察的点肯定不是排序这种简单的方式。



解法 2



我们在学排序算法时,有一种方法是快排。其中有一个关键步骤叫做 partiton,即分区。也就是任意选定一个数,将小于它的数放在它前面,将大于等于它的数放在它后面,返回该数的位置,我们称之为基准点。这样,基准点就将待排序列分为了左右两部分。



分区后,从基准点开始,都是大于等于它的数。而我们知道基准点的位置,从而可以推算基准点是第几大的数。



因为我们只需要计算出第 k 大的数,并没有排序要求,所以完全可以借鉴分区的思路。



假设 len = 从基准点开始到数组末尾元素的总个数,则基准点是第 len 大的数。



  • len == k,那么基准点刚好是第 k 大的数。

  • len < k,那么说明结果肯定在左边,需要往基准点的左边找,且 k = k - len。这里需要注意更新 k 值。

  • len > k,那么说明结果肯定在右边,需要往基准点的右边找,k 不变。



点击查看具体实现



解法 3



思路跟解法 2 有些相似。同样是选定一个基准点,将小于它的数放到它前面,大于等于它的数放到后面,但不使用分区算法。相对来说,更好理解一些,但需要额外的空间。



简单来说,就是将小于它的数放到数组 leftPart 中,将大于等于它的数放到另一个数组 rightPart 中,自身不放入。



假设 k = rightPart.length + 1



  • len == k,那么基准点即为结果。

  • len < k,那么在 leftPart 中找,同样 k = k - len

  • len > k,那么在 rightPart 中找,k 不变。



点击查看具体实现



发布于: 2020 年 06 月 01 日 阅读数: 31
用户头像

liu_liu

关注

不要相信自己的记忆力 2017.11.13 加入

还未添加个人简介

评论

发布
暂无评论
# LeetCode 215. Kth Largest Element in an Array