//题目：给出一个数组，输出最小的k个数
//解法1：类似于快排的方式，找到index，知道index等于k时，前面的k个数就是最小的数
public class Main {
public static void main(String[] args) throws Exception {
getMaxNum(new int[]{4,5,1,6,2,7,3,8},5);
}
public static void getMaxNum(int[] input,int k){
int low = 0;
int high = input.length-1;
int mid = partition(input,low,high);
while(mid != k){
if(mid>k){
mid = partition(input,low,mid-1);
}else{
mid = partition(input,mid+1,high);
}
}
for(int i = 0;i<k;i++){
System.out.print(input[i]+" ");
}
}
public static int partition(int[] input, int low ,int high){
int temp = input[low];
while(low<high){
while(low<high && temp<=input[high]){
high--;
}
input[low] = input[high];
while(low<high && temp>=input[low]){
low++;
}
input[high] = input[low];
}
input[low] = temp;
return low;
}
}
//解法2：先取k个数组成大根堆，然后与之后的数字进行比较，再进行堆的调整
public class Main {
public static void main(String[] args) throws Exception {
getMaxNum(new int[]{4,5,1,6,2,7,3,8,2,3},5);
}
public static void getMaxNum(int[] input,int k){
int[] result = new int[k];
for(int i = 0;i<k;i++){
result[i] = input[i];
}
buildMaxHeap(input,k);
for(int i = k;i<input.length;i++){
if(input[i]<input[0]){
input[0] = input[i];
adjustDown(input,k,0);
}
}
for(int i = 0;i<k;i++){
System.out.print(input[i]+" ");
}
}
public static void buildMaxHeap(int[] input, int k){
for(int i = (k-2)/2;i>=0;i--){
adjustDown(input,k,i);
}
}
public static void adjustDown(int[] input, int length, int k){
int temp = input[k];
for(int i = k*2+1;i<length;i = i*2){
if(i+1<length && input[i+1]>input[i]){
i = i+1;
}
if(temp>=input[i]){ //构建大根堆是和之前要调整的原始结点值相比
break;
}else{
input[k] = input[i];
k = i;
}
}
input[k] = temp;
}
}
