jz40.最小的k个数

题目描述

题解

堆

想要获得一个数组中的最小的K个数, 可以使用堆结构完成该功能. 创建一个小根堆, 每添加一个元素, 其顶部元素都是所有元素中最小的.

先将所有元素都压入堆中, 然后弹出K次, 便得到了最小的K个数

public int[] getLeastNumbers2(int[] arr, int k) {
    PriorityQueue<Integer> queue = new PriorityQueue<>((a, b) -> {
        return a.compareTo(b);
    });
    for (int i : arr) {
        queue.add(i);
    }
    int[] res = new int[k];
    for (int i = 0; i < k; i++) {
        res[i] = queue.poll();
    }
    return res;

}

快排

其实最直观的方法就是先将数组排序, 然后输出最小的k个数.

我们都知道快排的算法原理, 用来解决该问题非常合适. 快排每次都会对数组进行切分, 切分后的数组就是完成了类似荷兰国旗的处理.

对返回的下标数值进行分析, 如果正好等于K, 那么K左边的数就是我们要求的

public int[] getLeastNumbers(int[] arr, int k) {
    int len = arr.length;

    quickSort(arr, 0, len - 1, k);
    return Arrays.copyOfRange(arr, 0, k);
}

private void quickSort(int[] arr, int left, int right, int k) {
    if (left > right) {
        return;
    }

    int pIndex = partition(arr, left, right);
    if (pIndex == k) {
        return;
    } else if (pIndex < k) {
        quickSort(arr, pIndex + 1, right, k);
    } else {
        quickSort(arr, left, pIndex - 1, k);
    }
}

private int partition(int[] arr, int left, int right) {
    int pivot = arr[left];
    int lt = left;
    for (int i = left + 1; i <= right; i++) {
        if (arr[i] < pivot) {
            lt++;
            swap(arr, lt, i);
        }
    }
    swap(arr, left, lt);
    return lt;
}

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