刷题
刷题
learn
learn
日期
Aug 30, 2024
无需数组中找第K大的数
给定整数数组
nums 和整数 k ，请返回数组中第 k 大的元素。请注意，你需要找的是数组排序后的第
k 个最大的元素要求：时间复杂度为
利用改写快排的方法，时间复杂度为，额外空间复杂度为
上面问题的解法就是随机选择算法，是常考内容！定量证明见《算法导论》-9.2
《算法导论》第九章，还有一个BFPRT算法，不用随机选择一个数的方式，也能做到时间复杂度，额外空间复杂度
- 思路：在随机快排的基础上，每次排完了就检查一下
x的下标；比如如果想找第2大的数，那么目标下标就是倒数第二个位置，每次排完就比较x下标，如果小于倒数第二个位置就到右边接着排，否则就到左边排；命中就是x对应的下标包在left和right之间，这时候返回