问题：

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

解决：

① 直接使用api排序，O（nlogn）。

① 借助快排，但是前k个数可能会无序，O（n）。

import java.util.ArrayList;

import java.util.Collections; public class Solution {     public static ArrayList<Integer> GetLeastNumbers_Solution(int [] input, int k) {         ArrayList<Integer> res = new ArrayList<>();         if(input == null || input.length <= 0 || k <= 0 || k > input.length){             return res;         }         int start = 0;         int end = input.length - 1;         int index = partition(input,start,end);         while(index != k - 1){             if (index > k - 1){                 end = index - 1;                 index = partition(input,start,end);             }else {                 start = index + 1;                 index = partition(input,start,end);             }         }         for (int i = 0;i < k;i ++){             res.add(input[i]);         }         //Collections.sort(res);         return res;     }     public static int partition(int[] input,int start,int end){         int pivot = input[start];         while(start < end){             while(start < end && input[end] >= pivot){                 end --;             }             input[start] = input[end];             while(start < end && input[start] <= pivot) {                 start ++;             }             input[end] = input[start];         }         input[end] = pivot;         return end;     } }

③ 基于堆或者红黑树。O（nlogk），适合处理海量数据。

先创建一个大小为 k 的数据容器来存储最小的 k 个数字，接下来我们每次从输入的 n 个整数中读入一个数．如果容器中已有的数字少于 k 个，则直接把这次读入的整数放入容器之中：如果容器中己有k 数字了，也就是容器己满，此时我们不能再插入新的数字而只能替换已有的数字。找出这己有的 k 个数中的最大值，然后 1 在这次待插入的整数和最大值进行比较。如果待插入的值比当前己有的最大值小，则用这个数替换当前已有的最大值：如果待插入的值比当前已有的最大值还要大，那么这个数不可能是最小的k个整数之一，于是我们可以抛弃这个整数。

因此当容器满了之后，我们要做 3 件事情： 一是在 k 个整数中找到最大数： 二是有可能在这个容器中删除最大数： 三是有可能要插入一个新的数字。我们可以使用一个大顶堆在 O(logk）时间内实现这三步操作。

import java.util.ArrayList;

import java.util.PriorityQueue; public class Solution {     public static ArrayList<Integer> GetLeastNumbers_Solution(int [] input, int k) {         ArrayList<Integer> res = new ArrayList<>();         if(input == null || input.length <= 0 || k <= 0 || k > input.length){             return res;         }         PriorityQueue<Integer> queue = new PriorityQueue<>((o1,o2) -> {return o2 - o1;});//大顶堆         for (int i = 0;i < input.length;i ++){             if (queue.size() < k){                 queue.offer(input[i]);             }else {                 if (input[i] < queue.peek()){                     queue.poll();                     queue.offer(input[i]);                 }             }         }         while(! queue.isEmpty()){             int cur = queue.poll();             res.add(0,cur);         }         return res;     } }

③ 使用小顶堆

import java.util.ArrayList;

import java.util.PriorityQueue;

public class Solution {

    public static void main(String[] args){         int[] input = {4,5,1,6,2,7,3,8};         ArrayList<Integer> res = GetLeastNumbers_Solution(input,4);         System.out.println(res.toString());     }     public static ArrayList<Integer> GetLeastNumbers_Solution(int [] input, int k) {         ArrayList<Integer> res = new ArrayList<>();         if (input == null || input.length == 0 || k > input.length){             return res;         }         PriorityQueue<Integer> priorityQueue = new PriorityQueue<>((o1, o2) -> o1 - o2);         for (int n : input){             priorityQueue.offer(n);         }         for (int i = 0;i < k;i ++){             res.add(priorityQueue.poll());         }         return res;     } }