package new_offer;
import java.util.ArrayList;
import com.sun.net.httpserver.Authenticator.Result;
/**
*
输入n个整数，找出其中最小的K个数。
例如输入4,5,1,6,2,7,3,8这8个数字，则最小的4个数字是1,2,3,4,。
* @author Sonya
* 方法一：借助排序，排完之后想要几个有几个
* 方法二：借助O（n）当可以修改输入数组时可用
* 方法三:O(nlogK)算法，适合处理海量数据。
*
*/
public class N29_GetLeastNumbers_Solution {
public ArrayList<Integer> GetLeastNumbers_Solution(int [] input, int k) {
ArrayList<Integer> result=new ArrayList<Integer>();
if(k>input.length)return result;
sort(input,0,input.length-1);
for(int i=0;i<k;i++) {
result.add(input[i]);
}
return result;
}
//快排
public static void sort(int[] a, int low, int high) {
if(low>=high)
return;
int i = low;
int j = high;
int key = a[i];
while(i<j){
while(i<j&&a[j]>=key){
j--;
}
if(i<j){
a[i++]=a[j];
}
while(i<j&&a[i]<=key){
i++;
}
if(i<j){
a[j--]=a[i];
}
}
a[i] = key;
sort(a,low,i-1);
sort(a,i+1,high);
}
public static void main(String[] args) {
// TODO Auto-generated method stub
N29_GetLeastNumbers_Solution n29=new N29_GetLeastNumbers_Solution();
int []a= {4,5,1,6,2,7,3,8};
n29.GetLeastNumbers_Solution(a, 4);
for(int i=0;i<a.length;i++) {
System.out.println(a[i]);
}
System.out.println(a);
}
}
转载于:https://www.cnblogs.com/kexiblog/p/11151094.html
