老师打扰您了，LetCode第251号问题数组中第K个最大元素，用您说的partition如何思考这个问题呢？我感觉我自己思路给堵住了。谢谢您
来源：3-5 三路快排partition思路的应用 Sort Color
JasperJiao
2020-03-04
老师打扰您了，LetCode第251号问题数组中第K个最大元素，用您说的partition如何思考这个问题呢？我感觉我自己思路给堵住了。谢谢您
class Solution {
public int findKthLargest(int[] nums, int k) {
return partition(nums, nums.length-k, 0, nums.length-1);
}
public int partition(int[] nums, int k, int s, int e) {
int i = s;
int j = e;
int flag = nums[s];
while(i<j) {
while(i<j && nums[j]>=flag) {
j–;
}
swap(nums, i, j);
while(i<j && nums[i]<=flag) {
i++;
}
swap(nums, i, j);
}
** //写的partition的左右边界的取值我有些不太能理解望您指点**
if(i == k) return flag;
else if(i > k) return partition(nums, k, s, i-1);
else return partition(nums, k, i+1, e);
}
public void swap(int[] N, int i, int j) {
int tmp = N[i];
N[i] = N[j];
N[j] = tmp;
}
}.
1回答
-
liuyubobobo
2020-03-04
我在我的课程《玩转算法和数据结构》中曾经提供过一个基于 partition 求解第 k 小元素的代码，里面有详细的注释，可以参考：https://github.com/liuyubobobo/Play-with-Algorithms/blob/master/03-Sorting-Advance/Course%20Code%20(C%2B%2B)/Optional-05-Selection/main.cpp
注意，上面的代码不是这个问题的代码，但我相信可以非常好地帮助你理解如何使用 partition 就觉第 k 大/小的问题。
如果还有不理解的地方，你必须详细地表述出你的问题，具体在哪一句或者哪一段？你是怎么想的？认为应该怎么写？但对于什么测试用例，你认为这样写，某个变量的结果应该是什么？实际却是什么？
加油！：）
112020-03-04
相似问题