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回答

liuyubobobo

2024-01-11

在包含有大量相同元素的情况下,基于随机的单路快排的思路也会超时。力扣之前这个问题没有大量相同元素的测试用例,应该是最近添加了,尝试一下把 partition 改成双路?


关于单路快排的性能问题,请参考这一章的第一小节:https://class.imooc.com/lesson/1582#mid=37044


继续加油!:)

0

算法与数据结构

波波老师5年集大成之作,算法与数据结构系统学习,考试、面试、竞赛通用

2610 学习 · 1087 问题

查看课程