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
继续加油!:)
相似问题