输入n个整数，找出其中最小的K个数。例如输入4,5,1,6,2,7,3,8这8个数字，则最小的4个数字是1,2,3,4。
解题思路 StreamAPI方式直接使用sortAPI，有点慢。
时间复杂度O(nlogn)
利用Partition函数解题不断partition，直到找到下标k-1，然后输出前k个数字。
时间复杂度为O(n)；不好的地方在于会改变原数组。
利用堆解题 利用数组建堆构建一个k大小的大顶堆，当之后的元素大于堆顶元素，则抛弃堆顶，让该元素入堆。
使用PriorityQueue利用java的PriorityQueue来建立小顶堆，接着poll取k个数。
时间复杂度为O(nlogk)，空间复杂度O(k)，适合用于处理大数据
利用红黑树解题构建一个k大小的红黑树，之后的原理和堆一样
时间复杂度为O(nlogk)，空间复杂度O(k)，适合用于处理大数据
我们这里采用基于黑红树实现的数据结构TreeSet实现
代码 StreamAPI方式import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.stream.Collectors;
public class GetLeastNumbers1 {
public static ArrayList getLeastNumbers(int[] input, int k) {
if (input == null || input.length == 0 || k > input.length || k < 0) {
return null;
}
List list = Arrays.stream(input).boxed().sorted().limit(k).collect(Collectors.toList());
return (ArrayList) list;
}
public static void main(String[] args) {
int[] nums = {4,5,1,6,2,7,3,8};
ArrayList leastNumbers = getLeastNumbers(nums, 4);
System.out.println(leastNumbers);
}
}
利用Partition函数解题
import java.util.ArrayList;
public class GetLeastNumbers2 {
public static ArrayList getLeastNumbers(int[] input, int k) {
if (input == null || input.length == 0 || k > input.length || k < 0) {
return null;
}
ArrayList arrayList = new ArrayList<>();
int start = 0;
int end = input.length - 1;
// 获取基准的索引
int index = partition(input, input.length, start, end);
// 直到基准索引=k-1
while (index != k-1) {
if (index > k-1) {
// 如果基准索引>k-1，那么就在基准的左侧遍历
end = index - 1;
index = partition(input, input.length, start, end);
} else {
// 如果基准索引= length)
return -1;
// 随机选择一个下标，将对应的元素移到最后；实现代码在后面
int index = randomInRange(start, end);
// 交换数组中两个元素的值，实现代码在后面
swap(data, index, end);
// 最终返回的 small 是随机选择的下标（此时的数组元素值改变为：所有比选择的下标对应的元素大的
// 都被移到数组的右边，比选择的下标对应的元素小的都在数组的左边）
// small 用作下标，作用：在small左边的元素都是 < 随机选择的下标对应的元素
int small = start - 1;
for (index = start; index < end; index++) {
// index也相当于一个下标，从start开始向前遍历，
// 当下标 index 对应元素比data[end]小时，small++；
if (data[index] < data[end]) {
// small未++前，下标 small 前的元素都比data[end]小
++small;
// 当 index 比 small 大时（此种情况出现在遍历过程中data[index] >= data[end],
// index继续后移，small不变）
// 此时++small后,small为第一个比data[end]大的元素下标，
// 交换 index 与 small 的位置
if (small != index)
swap(data, small, index);
}
}
// for循环结束后，index指向end
// ++small之后，small指向一个比下标end对应元素大的数或者end元素本身
++small;
swap(data, small, end);
return small;
}
// 生成两个数之间的随机数，[min,max]
public static int randomInRange(int min, int max) {
return (int) (Math.random() * (max + 1 - min) + min);
}
// 交换数组中两个值
public static void swap(int[] data, int num1, int num2) {
int temp = data[num1];
data[num1] = data[num2];
data[num2] = temp;
}
// 测试
public static void main(String[] args) {
int[] nums = {4,5,1,6,2,7,3,8};
ArrayList leastNumbers = getLeastNumbers(nums, 4);
System.out.println(leastNumbers);
}
}
关于快速排序中的partition方法可以看这篇文章：
如何学习快速排序算法 for java_滕青山博客-CSDN博客
import java.util.ArrayList;
public class GetLeastNumbers3 {
public static ArrayList getLeastNumbers(int[] input, int k) {
// 防止特殊输入
if (input == null || input.length <= 0 || input.length < k || k < 1) {
return null;
}
ArrayList list = new ArrayList();
// 构建最大堆(从非叶节点开始)
for (int i = (k >> 1) - 1; i >= 0; i--) {
adjustMaxHeapSort(input, i, k - 1);
}
// 从第下标为k的元素开始分别与最大堆的最大值做比较，如果比最大值小，则替换并调整堆，
// 最终堆里的就是最小的k个数。
int tmp;
for (int i = k; i < input.length; i++) {
// 第i个数小于堆顶元素，则放入堆中
if (input[i] < input[0]) {
swap(input, 0, i);
adjustMaxHeapSort(input, 0, k - 1);
}
}
for (int j = 0; j < k; j++) {
list.add(input[j]);
}
return list;
}
public static void adjustMaxHeapSort(int[] input, int pos, int end) {
// 拿到左子节点
int child = (pos << 1) + 1;
while (child <= end) {
// 比较左右子节点，选出两个孩子较大的那个
if (child < end && input[child] < input[child + 1]) {
child = child + 1;
}
if (input[pos] < input[child]) {
swap(input, pos, child); // 孩子节点与当前节点替换
// 准备下一次循环
pos = child;
child = (pos << 1) + 1;
} else {
break;
}
}
}
public static void swap(int[] arr, int i, int j) {
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
// 测试
public static void main(String[] args) {
int[] nums = {4,5,1,6,2,7,3,8};
ArrayList leastNumbers = getLeastNumbers(nums, 4);
System.out.println(leastNumbers);
}
}
关于堆的学习：
java写一个堆排序（大顶堆）_两鬓已不能斑白的专栏-CSDN博客
import java.util.ArrayList;
import java.util.PriorityQueue;
public class GetLeastNumbers5 {
public static ArrayList getLeastNumbers(int[] input, int k) {
// 防止特殊输入
if (input == null || input.length <= 0 || input.length < k || k < 1) {
return null;
}
// 小顶堆
PriorityQueue minHeap = new PriorityQueue<>();
// 返回列表
ArrayList list = new ArrayList();
for (int i : input) {
minHeap.add(i);
}
for (int i = 0; i < k; i++) {
list.add(minHeap.poll());
}
return list;
}
// 测试
public static void main(String[] args) {
int[] nums = {4,5,1,6,2,7,3,8};
ArrayList leastNumbers = getLeastNumbers(nums, 4);
System.out.println(leastNumbers);
}
}
利用红黑树解题
TreeSet 是一个有序的集合，它的作用是提供有序的Set集合。
import java.util.ArrayList;
import java.util.Iterator;
import java.util.TreeSet;
public class GetLeastNumbers4 {
public static ArrayList getLeastNumbers(int[] input, int k) {
ArrayList list = new ArrayList();
// 防止特殊输入
if (input == null || input.length <= 0 || input.length < k || k < 1) {
return list;
}
// 利用TreeSet构建一颗k大小的黑红树
TreeSet treeSet = new TreeSet();
for (int i = 0; i < k; i++) {
treeSet.add(input[i]);
}
// 之后的数与红黑树最大值的比较，如果比最大值大，替换数中最大值
for (int i = k; i < input.length; i++) {
// 拿到树中的最大值
int max = treeSet.last();
if (input[i] < max) {
treeSet.remove(max);
treeSet.add(input[i]);
}
}
// 包装成list
Iterator it = treeSet.iterator();
while (it.hasNext()) {
list.add(it.next());
}
return list;
}
// 测试
public static void main(String[] args) {
int[] nums = {4,5,1,6,2,7,3,8};
ArrayList leastNumbers = getLeastNumbers(nums, 4);
System.out.println(leastNumbers);
}
}
来自：
《剑指Offer》
Coding-Interviews/最小的k个数.md at master · todorex/Coding-Interviews
