题目描述
输入n个整数，输出其中最小的k个。
详细描述：
接口说明
原型：
bool GetMinK(unsignedint uiInputNum, int * pInputArray, unsignedint uiK, int * pOutputArray);
输入参数：
unsignedint uiInputNum //输入整数个数
int * pInputArray //输入整数数组
unsignedint uiK //需输出uiK个整数
输出参数（指针指向的内存区域保证有效）：
int * pOutputArray //最小的uiK个整数
返回值：
false 异常失败
true 输出成功
输入描述:
输入说明
1 输入两个整数
2 输入一个整数数组
输出描述:
输出一个整数数组
示例1
输入
5 2
1 3 5 7 2
输出
1 2
代码如下：
package com.yzh.hehe;
import java.util.Scanner;
public class OutputNMin {
/*
* 先以o(n)时间建一个堆，再依次删除k个堆顶值
*
* */
public static void main(String[] args) {
Scanner scanner=new Scanner(System.in);
while ( scanner.hasNext()) {
int size=scanner.nextInt();
int k=scanner.nextInt();
int[]arr=new int[size+1];
int temp;
for (int i = 1; i <= size; i++) {
temp=scanner.nextInt();
insertHeap(arr, temp,i);
}
for (int i = 0; i < k; i++) {
deleteHeapMain(arr, size-i);
}
int p=size-k+1;
for (int i =size ; i >p; i--) {
System.out.print(arr[i]);
System.out.println(" ");
}
System.out.print(arr[p]);
}
scanner.close();
}
//建堆 执行n次建堆操作O(n)
private static void insertHeap(int[] arr,int value,int p) {
int i;
for ( i = p; i>1&&arr[i/2]>value; i=i/2) {
arr[i]=arr[i/2];
}
arr[i]=value;
}
//删除堆顶值（最小值）
private static void deleteHeapMain(int[]arr,int length) {
int reV=arr[1];//删除第一个值
int lastV=arr[length];
int i,child;
//2*i <=length保证空格还没下沉到最底层
for (i = 1; 2*i <=length ;i=child ) {
child=2*i;
if(child!=length&&(arr[2*i]>arr[2*i+1])){
child++; //判断走左还是走右
}
//判断是否能将最后一个值插入到目前的空格
if(lastV>arr[child]){
arr[i]=arr[child];
}else{
break;
}
}
arr[i]=lastV; //插入最后一个值
arr[length]= reV;//用来存储删除的第一个值
}
}