bobo老师，为啥三路快排的思想在程序员面试经典就要超时呢？代码如下

    public int[] getLeastNumbers(int[] arr, int k) {
        if (k == 0) {
            return new int[0];
        }
        return getLeastNumbers(arr, 0, arr.length - 1, k);
    }

    private int[] getLeastNumbers(int[] arr, int l, int r, int k) {
        int idx = new Random().nextInt(r - l + 1) + l;
        swap(arr, idx, l);
        // arr[l+1,lt]<arr[l] arr[lt+1,i-1]=arr[l] arr[gt,r]>arr[l]
        int lt = l, i = l + 1, gt = r + 1;
        while (i < gt) {
            if (arr[i] == arr[l]) {
                i++;
            } else if (arr[i] > arr[l]) {
                gt--;
                swap(arr, i, gt);
            } else {
                lt++;
                swap(arr, i, lt);
                i++;
            }
        }
        swap(arr, lt, l);
        if (lt == k - 1) {
            return Arrays.copyOf(arr, k);
        } else if (lt < k - 1) {
            return getLeastNumbers(arr, l + 1, r, k);
        } else {
            return getLeastNumbers(arr, l, r - 1, k);
        }
    }

    private void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }

我要跳槽 2022-02-02

源自：快速排序法 2-10 和 Select K 相关的三个问题

收起

1回答

liuyubobobo 2022-02-02 12:55:02

请给我问题链接和完整可以提交的代码，谢谢。

==========

你的递归过程，每次只会将处理的区间 -1（l + 1 或者 r - 1），所以最差情况下，整个递归函数会执行 n 层。而整个递归函数的时间是 O(n) 的，所以算法整体是 O(n^2) 的。

请先仔细理解这里我提供的基于双路排序的 selectK 问题的代码。递归过程，每次能排除掉“一半”的元素：https://class.imooc.com/lesson/1582#mid=37054

以下代码是我根据你的代码修改的可以 ac 的代码，注意在递归过程中的变化（注释部分）：

class Solution {

    public int[] smallestK(int[] arr, int k) {
        if (k == 0) {
            return new int[0];
        }
        getLeastNumbers(arr, 0, arr.length - 1, k);
        return Arrays.copyOf(arr, k);
    }

    private void getLeastNumbers(int[] arr, int l, int r, int k) {
        int idx = new Random().nextInt(r - l + 1) + l;
        swap(arr, idx, l);
    
        // arr[l+1,lt]<arr[l] arr[lt+1,i-1]=arr[l] arr[gt,r]>arr[l]
        int lt = l, i = l + 1, gt = r + 1;
        while (i < gt) {
            if (arr[i] == arr[l]) {
                i++;
            } else if (arr[i] > arr[l]) {
                gt--;
                swap(arr, i, gt);
            } else {
                lt++;   
                swap(arr, i, lt);
                i++;
            }
        }
        
        swap(arr, lt, l);
       
        // 每次递归可以或者排除掉 lt 端的所有元素，
        // 或者排除掉 gt 端的所有元素
        if(k - 1 <= lt - 1){
            getLeastNumbers(arr, l, lt - 1, k);
        }
        else if(k - 1 >= gt){
            getLeastNumbers(arr, gt, r, k);
        }
    }

    private void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
}

继续加油！：）

收起回答

提问者我要跳槽 #1

问题连接：https://leetcode-cn.com/problems/smallest-k-lcci/
class Solution {    
    public int[] smallestK(int[] arr, int k) {        
        if (k == 0) {            
            return new int[0];
        }        
        return getLeastNumbers(arr, 0, arr.length - 1, k);
    }    
    private int[] getLeastNumbers(int[] arr, int l, int r, int k) {        
        int idx = new Random().nextInt(r - l + 1) + l;
        swap(arr, idx, l);        
        // arr[l+1,lt]<arr[l] arr[lt+1,i-1]=arr[l] arr[gt,r]>arr[l]
        int lt = l, i = l + 1, gt = r + 1;        
        while (i < gt) {            
            if (arr[i] == arr[l]) {
                i++;
            } else if (arr[i] > arr[l]) {
                gt--;
                swap(arr, i, gt);
            } else {
                lt++;
                swap(arr, i, lt);
                i++;
            }
        }
        swap(arr, lt, l);        
        if (lt == k - 1) {            
            return Arrays.copyOf(arr, k);
        } else if (lt < k - 1) {            
            return getLeastNumbers(arr, l + 1, r, k);
        } else {            
            return getLeastNumbers(arr, l, r - 1, k);
        }
    }    
    private void swap(int[] arr, int i, int j) {        
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }

}

2022-02-02 15:40:34