最小的k个数

题目

设计一个算法，找出数组中最小的k个数。以任意顺序返回这k个数均可。

示例：

输入： arr = [1,3,5,7,2,4,6,8], k = 4
输出： [1,2,3,4]

解题思路

解法1：
快排后取前k个数
解法2：大顶堆|小顶堆
长度为k，利用内部的堆排序一次性找出最小k个数。
java特有的东西，之前都没见过，但快排O(logn+k)，用堆执行起码得把数组都过一遍，不会比快排快，所以先贴上代码，当熟悉下。

class Solution {
    public int[] smallestK(int[] arr, int k) {
        quickSort(arr,0,arr.length - 1);
        int[] res = new int[k];
        for (int i = 0; i <k ; i++){
            res[i] = arr[i];
        }
        return res;
    }

    public void quickSort (int[] arr, int left, int right){
        if (left > right) return;
        int i = left;
        int j = right;
        int value = arr[left];
        while (i < j){
            while(value <= arr[j] && i<j){
                j--;
            }
            while (value >= arr[i] &&i<j){
                i++;
            }
            if (i < j){
                int temp = arr[i];
                arr[i] = arr[j];
                arr[j] = temp;
            }
        }
        arr[left] = arr[j];
        arr[j] = value;
        quickSort(arr,left,j-1);
        quickSort(arr,j+1,right);
    }
}

class Solution {
    public int[] smallestK(int[] arr, int k) {
        PriorityQueue<Integer heap = new PriorityQueue<Integer>(k+1);
        for (int num: arr){
              heap.offer(num); //压入堆，内部排序后将大值踢出。
        }
         int[] res = new int[k];
        for (int i = 0; i <k ; i++){
            res[i] = heap.poll(); //遍历输出
        }
        return res;
    }
}

作者：xiaoxiaoyuxie
链接：https://leetcode-cn.com/problems/smallest-k-lcci/solution/kuai-pai-by-xiaoxiaoyuxie/
来源：力扣（LeetCode）