考点：时间效率、数组、高级算法
题目描述
输入n个整数，找出其中最小的K个数。例如输入4,5,1,6,2,7,3,8这8个数字，则最小的4个数字是1,2,3,4,。
代码格式
public class Solution {
public ArrayList<Integer> GetLeastNumbers_Solution(int [] input, int k) {
}
}
解题一-
1.思路
设置一个大小为k的容器，如果还有空余，就将数组中的数加进去，否则就比较数组中的数和容器中最大的数，选择最小的放进去。
注：ArrayList中的indexOf（int k）方法，是返回值为k的下标。
2.代码
import java.util.ArrayList;
import java.util.Collections;
public class Solution {
public ArrayList<Integer> GetLeastNumbers_Solution(int [] input, int k) {
ArrayList<Integer> result = new ArrayList<>();
int lens = input.length;
//参数满足条件
if(input == null || lens == 0 || k > lens || k <= 0){
return result;
}
for(int i = 0; i < input.length; i++) {
if(res.size() < k) {
res.add(input[i]);
}
else {
int max = Collections.max(res);
if(max > input[i]) {
res.set(res.indexOf(max), input[i]);
}
}
}
return res;
}
}
参考：原文链接：https://blog.csdn.net/melwx/article/details/88629440
解题二-利用快速排序的partition()方法
1.思路
（1）利用快排的partition函数,将原序列分为左右两个子序列，左边序列都小于array[index]，右边序列都大于或等于array[index]
（2）遍历数组，当array[index]为数组的第k个元素时，数组中array[index]及其之前的元素都小于右边序列，即为n个整数中最小的k个数。使用大小为k的堆，维护到目前为止最小的k个数。
2.代码
import java.util.ArrayList;
public class Solution {
public ArrayList<Integer> GetLeastNumbers_Solution(int [] input, int k) {
ArrayList<Integer> result = new ArrayList<>();
int lens = input.length;
//参数满足条件
if(input == null || lens == 0 || k > lens || k <= 0){
return result;
}
//// 快排思想，index前面的数小于input[index]
int index = partition(input, 0, lens-1);
// 目标索引,此处不能以k为目标索引，因为k可能等于数组的长度，以k为索引，数组越界
while(index != k-1){
// 目标值在index左侧
if(index > k-1)
index = partition(input, 0, index-1);
// 目标值在index右侧
if(index < k-1)
index = partition(input, index+1, input.length-1);
}
for(int i=0; i<=index; i++)
result.add(input[i]);
return result;
}
//partition()快速排序方法
// 以array[index]为参照，比该值小的放在左侧，比该值大的放在右侧，并返回array[left]的索引
public int partition(int[] array, int left, int right){
int random = (int)(Math.random()*(right - left + 1)) + left;
swap(array, random, right);
int small = left-1;//小于区 (最开始写错了小于区的初始值!)
int big = right;//大于区
while(left < big){
if(array[left] < array[right])
swap(array, left++, ++small);
else if(array[left] > array[right])
swap(array, left, --big);
else
left++;
}
swap(array, big, right);
return big;
}
//swap()方法
public void swap(int[] array, int i, int j){
int temp = array[i];
array[i] = array[j];
array[j] = temp;
}
}
参考：https://blog.csdn.net/littlehaes/article/details/92805711
解题三-构建最大堆容器
1.思路
（1）使用最大堆，构建容量为K的最大堆；
（2）遍历数组，每次比较数组中的元素与堆顶元素大小，堆顶小入堆
2.代码
import java.util.ArrayList;
import java.util.Comparator;
import java.util.PriorityQueue;
public class Solution {
public ArrayList<Integer> GetLeastNumbers_Solution(int [] input, int k) {
ArrayList<Integer> result = new ArrayList<>();
int lens = input.length;
//参数满足条件
if(input == null || lens == 0 || k > lens || k <= 0){
return result;
}
// 构建大顶堆
PriorityQueue<Integer> maxHeap = new PriorityQueue<>(k, new Comparator<Integer>(){
public int compare(Integer o1,Integer o2) {
return o2.compareTo(o1);
}
});
// 遍历数组，把比堆顶元素小的元素加入最大堆中
for (int i=0; i<lens; i++) {
int curVal = input[i];
if (maxHeap.size() < k) {
maxHeap.add(curVal);
} else {
// 堆顶元素大于当前元素，则弹出堆顶元素，加入当前元素到堆中
if (maxHeap.peek() > curVal) {
maxHeap.poll();
maxHeap.add(curVal);
}
}
}
// 最大堆所有元素加入要返回的list中
result.addAll(maxHeap);
return result;
}
public static void main(String[] args)
{
int[] input = {4,5,1,6,2,7,3,8};
System.out.println(new Solution().GetLeastNumbers_Solution(input, 4));
}
}
参考：https://blog.csdn.net/zangdaiyang1991/article/details/90318768
