LeetCode215 用快排递归的方式,用例跑完了,说我耗时太长,怎么优化啊?
来源:2-9 作业:Select K 问题
数据结构呆瓜
2023-12-30 14:25:54
麻烦老师帮我看一下代码问题在哪。我实在想不出了
public int findKthLargest(int[] nums, int k) {
// 从大到小的数组,第K大,意味着索引是k-1
Random random = new Random();
int l = 0; int r = nums.length - 1;
return mySelectK(nums, k, l, r, random);
}
public int mySelectK(int[] nums, int k, int l , int r, Random random) {
// 从大到小的数组,第K大,意味着索引是k-1
int partition = partition(nums,l,r,random);
if (k-1 == partition) {
return nums[partition];
}
else if (k-1 < partition) {
return mySelectK(nums, k, l, partition - 1, random);
}
else {
return mySelectK(nums,k,partition + 1, r, random);
}
}
/**
* patition左边大,右边小。
*/
public int partition(int[]nums, int l, int r ,Random random) {
int v = l;
int split = l;
int cur;
int p = l + random.nextInt(r - l + 1);
swap(nums,p,l);
for (cur = l + 1; cur <= r ; cur++) {
if (nums[cur] > nums[v]) {
split++;
swap(nums, cur, split);
}
}
swap(nums,split,v);
return split;
}
/**
* 交换数组中指定索引的元素位置
*/
private void swap(int[]nums, int x, int y) {
int temp = nums[x];
nums[x] = nums[y];
nums[y] = temp;
}翻译
搜索
复制
1回答
在包含有大量相同元素的情况下,基于随机的单路快排的思路也会超时。力扣之前这个问题没有大量相同元素的测试用例,应该是最近添加了,尝试一下把 partition 改成双路?
关于单路快排的性能问题,请参考这一章的第一小节:https://class.imooc.com/lesson/1582#mid=37044
继续加油!:)
相似问题