题目来源:https://leetcode.com/problems/kth-largest-element-in-an-array/
题目难度:Medium
解答1[Java]:
1 | import java.util.Arrays; |
但是这个实现依赖了 Java 的库,并不是一个通用的解法。
解答2
1 | //move the k largest elements to the left part of array |
要理解这个算法需要对快速排序算法有所了解。
每次 partition 之后,pivotPos 左边的元素都是大于 pivotPos的,右边的都是小于 PivotPos的,根据 pivotPos的index 和 k 的关系就能确定如果要继续寻找是在 pivotPos 左边寻找还是右边寻找。