（头条）
最小的第K个数也是和这题topK一样的思路
1、全排序 时间复杂度O（nlogn）
2、Partiton思想 时间复杂度O(n) （因为不需要像快排一样对所有的分段都两两Partition）
基于数组的第k个数字来调整，使得比第k个数字小的所有数字都位于数组的左边，比第k个数字大的所有数字都位于数组的右边。调整之后，位于数组左边的k个数字就是最小的k个数字（这k个数字不一定是排序的）。O(N)
3、最大堆 时间复杂度O（nlogk）
Java堆用优先队列PriorityQueue实现
4、如果用冒泡排序，时间复杂度为O(n*k)
1、全排序 时间复杂度O（nlogn）
Arrays.sort()
3、最大堆 时间复杂度O（nlogk）
用最大堆保存这k个数，每次只和堆顶比，如果比堆顶小，删除堆顶，新数入堆。
链接：https://www.nowcoder.com/questionTerminal/6a296eb82cf844ca8539b57c23e6e9bf
来源：牛客网 import java.util.ArrayList;
import java.util.PriorityQueue;
import java.util.Comparator;
public class Solution {
public ArrayList<Integer> GetLeastNumbers_Solution(int[] input, int k) {
ArrayList<Integer> result = new ArrayList<Integer>();
int length = input.length;
if(k > length || k == 0){
return result;
}
PriorityQueue<Integer> maxHeap = new PriorityQueue<Integer>(k, new Comparator<Integer>() { @Override
public int compare(Integer o1, Integer o2) {
return o2.compareTo(o1);
}
});
for (int i = 0; i < length; i++) {
if (maxHeap.size() != k) { //堆（优先队列加满后才出队）
maxHeap.offer(input[i]);
} else if (maxHeap.peek() > input[i]) {
Integer temp = maxHeap.poll();
temp = null;
maxHeap.offer(input[i]);
}
}
for (Integer integer : maxHeap) {
result.add(integer);
}
return result;
}
}
2、Partiton思想 时间复杂度O(n)
链接：https://www.nowcoder.com/questionTerminal/6a296eb82cf844ca8539b57c23e6e9bf
利用快速排序中的获取分割（中轴）点位置函数Partitiion。
基于数组的第k个数字来调整，使得比第k个数字小的所有数字都位于数组的左边，比第k个数字大的所有数字都位于数组的右边。调整之后，位于数组左边的k个数字就是最小的k个数字（这k个数字不一定是排序的）
时间复杂度O(n) ：一遍partition是O(N)的很容易证明。求第k大数的时候，pivot的不满足条件的那一侧数据不需要再去处理了，平均时间复杂度为O(N+N/2+N/4+...)=O(N)。而快排则需要处理，复杂度为O(nlogn)。
import java.util.*;
public class Solution {
public ArrayList<Integer> GetLeastNumbers_Solution(int [] input, int k) {
ArrayList<Integer> list = new ArrayList();
if(input.length==0||input.length<k||k<=0){
return list;
}
int index = partition(input,0,input.length-1,k);
int low = 0;
int high = input.length-1; while(index!=k-1){
if(index>k-1){
high = index-1;
index = partition(input,low,high,k);
}
else if(index<k-1){
low = index+1;
index = partition(input,low,high,k);
}
} for(int i=0;i<k;i++){
list.add(input[i]);
}
return list;
}
public int partition(int[] array,int low,int high,int k){
int temp = array[low];
while(low!=high){
while(low<high&&array[high]>=temp)
high--;
array[low] = array[high];
while(low<high&&array[low]<=temp)
low++;
array[high] = array[low];
}
array[low] = temp;
return low;
}
}