215
来源：3-5 三路快排partition思路的应用 Sort Color
pfco
2019-03-07
public int findKthLargest2(int[] nums, int k) {
fast(nums, 0, nums.length - 1);
return nums[nums.length - k];
}
private void fast(int[] nums, int i, int j) {
int low = i;
int high = j;
int key = nums[low];
while (low < high) {
if (low < high && nums[high] >= key) {
high--;
}
if (nums[high] < key) {
int temp1 = nums[high];
nums[high] = nums[low];
nums[low] = temp1;
}
if (low < high && nums[low] <= key) {
low++;
}
if (nums[low] > key) {
int temp2 = nums[low];
nums[low] = nums[high];
nums[high] = temp2;
}
}
while (low > i) {
fast(nums, i, low - 1);
}
while (high < j) {
fast(nums, high + 1, j);
}
}
老师我用的快速排序的解法，但是超出了时间的限制
写回答
1回答
-
liuyubobobo
2019-03-07
这段程序不是超时，而是有死循环。
直接使用下面的代码作为main函数，在你的本机运行一下，就会看到，你的程序是打印不出结果的。
public static void main(String[] main){ // 寻找 [1, 2, 3] 这个数组的第一小的元素 int[] num = {1, 2, 3}; System.out.println((new Solution()).findKthLargest2(num, 1)); }这个测试用例只有三个元素，足够的小，请仔细在你的环境中调试，看看自己的程序问题在哪里。调试程序可是学习算法，锻炼算法能力的重要一环哦。所有的人都不能一开始就写对所有的算法程序，不断的在调试中理解总结自己的逻辑漏洞，才能提高：）
关于这个问题，使用快排partition的思路，我的参考代码：https://github.com/liuyubobobo/Play-Leetcode/blob/master/0215-Kth-Largest-Element-in-an-Array/cpp-0215/main3.cpp
这个代码是使用C++的，但是基本逻辑是完全一致的。供参考。
加油！：）
00
相似问题