问题描述：
思路1：
下面给出快排序的代码（基于下面Partition函数的方法）
public void QuickSort(int[] arr, int start, int end){
if(start == end){
return;
}
int index = Partition(arr, start, end);
if(index > start){
QuickSort(arr, start, index - 1);
}
if(index < end){
QuickSort(arr, index + 1, end);
}
}相应的求最小的k个数的代码：
static boolean InvalidInput = false;
public ArrayList<Integer> GetLeastNumbers_Solution(int [] input, int k) {
ArrayList<Integer> result = new ArrayList<Integer>();
if(input == null || input.length == 0 || k > input.length || k <= 0){
InvalidInput = true;
return result;
}
int start = 0;
int end = input.length - 1;
QuickSort(input, start, end);
for(int i = 0; i < k; i++){
result.add(input[i]);
}
return result;
}思路2：（适合海量数据的输入）
关于容器的数据结构的选择：
- 数组：查找最大值需要O(k)
- 最大堆：查找最大值需要O(1),但需要O(logk)时间完成删除及插入操作。
- 红黑树
思路3：基于Partition,会改变原始数组
- 首先来看看Partition的原理与具体实现以及结果
基于上述Partition函数的解析，我们能用它来实现本文中的求最小的k个数
代码：
import java.util.ArrayList;
public class Solution {
static boolean InvalidInput = false;
public ArrayList<Integer> GetLeastNumbers_Solution(int [] input, int k) {
ArrayList<Integer> result = new ArrayList<Integer>();
if(input == null || input.length == 0 || k > input.length || k <= 0){
InvalidInput = true;
return result;
}
int start = 0;
int end = input.length - 1;
int index = Partition(input, start ,end);
while(index != k-1){
if(index > k - 1){
end = index - 1;
index = Partition(input, start ,end);
}else{
start = index + 1;
index = Partition(input, start, end);
}
}
for(int i = 0; i < k; i++){
result.add(input[i]);
}
return result;
}
public int Partition(int[] arr, int start, int end){
if(arr == null || arr.length == 0 || start < 0 || end < 0){
return -1;
}
int index = start + (int)(Math.random() * ((end - start) + 1));//随机选择一个作为标杆的数字
//将标杆放在数组最后一位
int tmp = arr[index]; arr[index] = arr[end]; arr[end] = tmp;
int small = start - 1;//small用来存储从右到左第一个小于标杆的数字的下标
for(index = start; index < end; index++){
if(arr[index] < arr[end]){//如果小于标杆
small++;//更新第一个小的
if(small != index){//如果当前遍历的不是第一个小的
tmp = arr[index];arr[index] = arr[small];arr[small] = tmp;//将当前遍历的数字放在第一个小的位置上
}
}
}
//由于small指示的是从右到左第一个小于标杆的，而此时标杆还放在数组最后，因此，应该将标杆放在small后面一位。
small++;
tmp = arr[small];arr[small] = arr[end]; arr[end] = tmp;
return small;//返回位置为所选择的标杆最后的位置
}
}