题目：输入n个整数，找出其中最小的K个数。例如输入4,5,1,6,2,7,3,8这8个数字，则最小的4个数字是1,2,3,4,。
package test; import java.util.ArrayList;
import java.util.Comparator;
import java.util.PriorityQueue; import org.junit.Test; public class GetLeastNumbers_Solution {
/**
* 基于优先队列，时间复杂度为o(nlogk)
*
* @param input
* @param k
* @return
*/
public ArrayList<Integer> GetLeastNumbers_SolutionPriorityQuene(
int[] input, int k) {
ArrayList<Integer> result = new ArrayList<Integer>();
if (input == null || input.length == 0 || k <= 0 || k > input.length)
return result;
PriorityQueue<Integer> maxHeap = new PriorityQueue<Integer>(
new Comparator<Integer>() {
@Override
public int compare(Integer o1, Integer o2) {
return o2.compareTo(o1);
}
});
for (int i = 0; i < k; i++) {
maxHeap.offer(input[i]);
}
for (int j = k; j < input.length; j++) {
if (input[j] < maxHeap.peek()) {
maxHeap.poll();
maxHeap.offer(input[j]);
}
}
for (Integer integer : maxHeap) {
result.add(integer);
} return result;
} /**
* 基于堆排序,时间复杂度为o(nlogk)
*
* @param input
* @param k
* @return
*/
public ArrayList<Integer> GetLeastNumbers_SolutionMaxHeap(int[] input, int k) {
ArrayList<Integer> result = new ArrayList<Integer>();
if (input == null || input.length == 0 || k <= 0 || k > input.length)
return result;
//构建最大堆
builtMaxHeap(input,k-1);
for (int i = k; i < input.length; i++) {
//数组k位后的数字比堆顶小
if (input[k] < input[0]) {
input[0] = input[k];
//调整堆
builtMaxHeap(input, k - 1);
}
}
for (int i = 0; i < k; i++) {
result.add(input[i]);
}
return result;
} /**
* 构建、调整最大堆
* @param a
* @param lastIndex
*/
public void builtMaxHeap(int[]a,int lastIndex){
int parentIndex = ((lastIndex-1) >> 1);
//从最后一个节点的父节点开始
for(int i=parentIndex;i>=0;i--){
//存在子节点
while (i*2+1<=lastIndex){
int leftIndex = i*2+1;
int rightIndex = i*2+2;
int biggerIndex = leftIndex;
//存在右结点
if (rightIndex <= lastIndex){
if(a[rightIndex] > a[biggerIndex]){
biggerIndex = rightIndex;
}
}
//子节点中最大节点大于父节点
if (a[biggerIndex] > a[i]){
swap(a,i,biggerIndex);
i = biggerIndex;
}else{
break;
}
}
}
} /**
* 基于Partition函数,时间复杂度为o(n),原数组已被修改
*
* @param input
* @param k
* @return
*/
public ArrayList<Integer> GetLeastNumbers_SolutionPartition(int[] input,
int k) {
ArrayList<Integer> result = new ArrayList<Integer>();
if (input == null || input.length == 0 || k <= 0 || k > input.length)
return result; int left = 0;
int right = input.length - 1;
int index = partition(input, 0, right); while (index != k - 1) {
if (index > k - 1) {
right = index - 1;
index = partition(input, left, right);
} else {
left = index + 1;
index = partition(input, left, right);
}
}
for (int i = 0; i < k; i++) {
result.add(input[i]);
} return result;
} /**
* partition函数
* @param a
* @param left
* @param right
* @return
*/
public int partition(int[] a, int left, int right) {
while (left < right) {
while (left < right && a[left] <= a[right]) {
right--;
}
if (left < right) {
swap(a, left, right);
}
while (left < right && a[left] <= a[right]) {
left++;
}
if (left < right) {
swap(a, left, right);
} }
return left;
} public void swap(int[] a, int i, int j) {
int tmp = a[i];
a[i] = a[j];
a[j] = tmp;
} @Test
public void testGetLeastNumbers_Solution() {
int[] a = { 4, 5, 1, 6, 2, 7, 3, 8 };
int k = 4;
ArrayList<Integer> list = GetLeastNumbers_SolutionPartition(a, k);
System.out.println(list.toString()); ArrayList<Integer> list2 = GetLeastNumbers_SolutionPriorityQuene(a, k);
System.out.println(list2.toString()); ArrayList<Integer> list3 = GetLeastNumbers_SolutionMaxHeap(a, k);
System.out.println(list3.toString()); }
}
除了基于优先队列，时间复杂度为O（nlogk）、堆排序，时间复杂度为O（nlogk）、partition函数，时间复杂度为O（n）的解法之外，还有基于冒泡排序的解法时间复杂度为（nk）。