最小的K个数【Java版】

方法一：k轮取最值（部分选择排序）
适合k非常小的情况；

import java.util.ArrayList;

public class Solution {
    public ArrayList<Integer> GetLeastNumbers_Solution(int [] input, int k) {
        ArrayList<Integer> res = new ArrayList<Integer>();
        if(k<=0 || k>input.length)return res;
        for(int i=0; i<=k-1; ++i){
            int min = Integer.MAX_VALUE;
            int index = 0;//标记这一轮的min的位置
            for(int j=0; j<=input.length-1; ++j){
                if(input[j] < min){
                    min = input[j];
                    index = j;
                }
            }
            res.add(min);
            input[index] = Integer.MAX_VALUE;//将此轮min给移除
        }
        return res;
    }
}
//时间复杂度：O(N*k)
//空间复杂度：O(k)

方法二：快排Partition思想
优点：平均时间O(N)
缺点：会在原数组上修改；输出的k个值无序； 最坏时间O(N^2)

import java.util.ArrayList;
public class Solution {
    public ArrayList<Integer> GetLeastNumbers_Solution(int [] input, int k) {
        ArrayList<Integer> res = new ArrayList<Integer>();
        if(k<=0 || k>input.length)return res;
        int divide = 0;
        int left =0;
        int right =input.length-1;
        while(true){
            divide = partition(input, left, right);
            if(divide > k-1){
                right=divide-1;
            }
            else if(divide < k-1){
                left = divide+1;
            }
            else if(divide == k-1)break; //到位(不能是k, k会溢出)
        }
        for(int i=0; i<=k-1; ++i){
            res.add(input[i]);
        }
        return res;
    }
    public int partition(int [] input, int left, int right){//【设计递归函数的原则：尽量精简】
        int temp = input[left];
        while(left<right){
            while(left<right && input[right]>=temp)--right;//注意【快排的大小判断 有等号】
            input[left] = input[right];//覆盖的时候，不需要移动下标
            while(left<right && input[left]<=temp)++left;
            input[right] = input[left];
        }
        input[left] = temp;
        return left;//此时left==right
    }
}
//时间复杂度分析：partition会遍历left~right;
//平均情况下：O(N)+O(N/2)+...+O(1)=O(2N)=O(N)
//最坏情况下：O(N)+O(N-1)+...+O(1)=O(N*(N-1)/2)=O(N^2)
//空间：max{O(logN),O(k)}
//1.快排栈深度是logN,每层空间O(1)  2.res占用空间

方法二延伸：非递归的partition方法

• 树状多分叉递归=》可转化为栈辅助非递归
• 线性递归=》可转化为：外加一层while循环；
  （要注意的是：递归使用的形参，如果外层也使用，则需要备份保存）

  import java.util.ArrayList;
  public class Solution {
    public ArrayList<Integer> GetLeastNumbers_Solution(int [] input, int k) {
        ArrayList<Integer> res = new ArrayList<Integer>();
        if(k > input.length || k<=0) return res;
        int left = 0;
        int right = input.length-1;
        while(left<right){
            int l = left;//保留left值
            int r = right;
            int temp = input[l];
            int divide =-1;//divide的作用是增加可读性
            while(l<r){
                while(l<r && input[r]>=temp)--r;//再次强调，快排中的等号不能少
                input[l] = input[r];
                while(l<r && input[l]<=temp)++l;
                input[r] = input[l];
            }
            input[l] = temp;
            divide = l;
            if(divide == k-1)break;
            else if(divide > k-1){
                right = divide-1;
            }
            else if(divide < k-1){
                left = divide+1;
            }
        }
        for(int i=0; i<=k-1; ++i){
            res.add(input[i]);
        }
        return res;
    }
  }

方法三：堆排序
——适合处理海量流数据 时间O(N*logK) 空间O(k)

//堆排序适合海量流数据，因为在运算的时候，允许后去不断输入、而不会破坏前面已经计算的结果
//使用Java的PriorityQueue基于堆；堆的规模是k,而不是N
//add/remove/poll操作的时间复杂度都是O(logK) ,peek复杂度是O(1)
//top-k问题：求最大用小根堆；求最小用大根堆。

import java.util.ArrayList;
import java.util.PriorityQueue;
import java.util.Collections;

public class Solution {
    public ArrayList<Integer> GetLeastNumbers_Solution(int [] input, int k) {
        ArrayList<Integer> res = new ArrayList<Integer>();
        if(k<=0 || input.length<k)return res;//【思路：先分再总】==>先分别考虑k和input，然后考虑之间关系
        //得到：if(k<=0 || input.length==0 || input.length < k)，然后将后两项合并
        PriorityQueue<Integer> maxRootHeap = new PriorityQueue<Integer>(k,Collections.reverseOrder());//堆初始化的时候必须要有参数(堆大小：大根/小根，默认小根堆)
        for(int i=0; i<=input.length-1; ++i){
            if(maxRootHeap.size()<k)//这里不能等于k
                maxRootHeap.add(input[i]);//开始时候直接入堆
            else if(maxRootHeap.peek()>input[i]){//大根堆的peek是堆中的最大值，如果input[i]比堆中最大值还大，就直接忽略
                maxRootHeap.poll();
                maxRootHeap.add(input[i]);
            }
        }
        for(int i=0; i<=k-1; ++i){
            res.add(maxRootHeap.poll());
        }
        return res;
    }
}
//时间复杂度O(Nlogk)
//空间复杂度O(k)==>大根堆的大小