# 具体遇到的问题

# 报错信息的截图

# 相关课程内容截图

# 尝试过的解决思路和结果

# 粘贴全部相关代码，切记添加代码注释（请勿截图）

public int[] getLeastNumbers(int[] arr, int k) {

    if (k == 0) {

        return new int[0];

    } else if (arr.length <= k) {

        return arr;

    }

    

    // 原地不断划分数组

    partitionArray(arr, 0, arr.length - 1, k);

    

    // 数组的前 k 个数此时就是最小的 k 个数，将其存入结果

    int[] res = new int[k];

    for (int i = 0; i < k; i++) {

        res[i] = arr[i];

    }

    return res;

}

void partitionArray(int[] arr, int lo, int hi, int k) {

    // 做一次 partition 操作

    int m = partition(arr, lo, hi);

    // 此时数组前 m 个数，就是最小的 m 个数

    if (k == m) {

        // 正好找到最小的 k(m) 个数

        return;

    } else if (k < m) {

        // 最小的 k 个数一定在前 m 个数中，递归划分

        partitionArray(arr, lo, m-1, k);

    } else {

        // 在右侧数组中寻找最小的 k-m 个数

        partitionArray(arr, m+1, hi, k);

    }

}

// partition 函数和快速排序中相同，具体可参考快速排序相关的资料

// 代码参考 Sedgewick 的《算法4》

int partition(int[] a, int lo, int hi) {

    int i = lo;

    int j = hi + 1;

    int v = a[lo];

    while (true) { 

        while (a[++i] < v) {

            if (i == hi) {

                break;

            }

        }

        while (a[--j] > v) {

            if (j == lo) {

                break;

            }

        }

        if (i >= j) {

            break;

        }

        swap(a, i, j);

    }

    swap(a, lo, j);

    // a[lo .. j-1] <= a[j] <= a[j+1 .. hi]

    return j;

}

作者：nettee

链接：https://leetcode-cn.com/problems/zui-xiao-de-kge-shu-lcof/solution/tu-jie-top-k-wen-ti-de-liang-chong-jie-fa-you-lie-/

来源：力扣（LeetCode）

著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

我想问下 为什么“swap(a, lo, j);”是lo和J交换而不是和i交换 我看快排里面都是和i交换的