40-最小的k个数

输入整数数组 arr ，找出其中最小的 k 个数。例如，输入4、5、1、6、2、7、3、8这8个数字，则最小的4个数字是1、2、3、4。

最简单的-排序

直接排序，然后取前k个即可。

 public int[] getLeastNumbers(int[] arr, int k) {
        if (arr == null || arr.length == 0 || k == 0) {
            return new int[0];
        }
        Arrays.sort(arr);
        int[] result = new int[k];
        for (int i = 0; i < k; i++) {
            result[i] = arr[i];
        }
        return result;
    }

快排思想

快排在每一次操作后，都会确定一个元素的位置，假如这个元素的索引刚好是k-1,那么说明前k个元素就是所需要的。

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

        int[] result = new int[k];
        for (int i = 0; i < k; i++) {
            result[i] = arr[i];
        }
        return result;
    }

    public void sort(int[] arr,int lo,int hi,int k) {
        if (lo >= hi) {
            return;
        }
        int partition = partition(arr, lo,hi);
        //如果找到了对应的partition则返回即可
        if (partition == k - 1) {
            return;
        }
        sort(arr, lo, partition - 1,k);
        sort(arr, partition + 1, hi,k);
    }


    public int partition(int[] arr, int start, int end) {
        int i = start;
        int pivot = arr[start];
        for (int j = start + 1; j <= end; j++) {
            if (arr[j] <= pivot) {
                swap(arr, ++i, j);
            }
        }
        swap(arr, start, i);
        return i;
    }
    public static void swap(int[] numbers, int i, int j) {
        int tmp = numbers[i];
        numbers[i] = numbers[j];
        numbers[j] = tmp;
    }

不过上面代码还是会进行多余的排序操作，实际上可以参考39里的快排使用方法。