题目：输入n个整数，找出其中最小的K个数。例如输入4,5,1,6,2,7,3,8这8个数字，则最小的4个数字是1,2,3,4。
练习地址
https://www.nowcoder.com/practice/6a296eb82cf844ca8539b57c23e6e9bf
https://leetcode-cn.com/problems/zui-xiao-de-kge-shu-lcof/
解法一：时间复杂度为 O(n) 的算法，只有当我们可以修改输入的数组时可用
import java.util.ArrayList;
public class Solution {
public ArrayList<Integer> GetLeastNumbers_Solution(int[] input, int k) {
ArrayList<Integer> result = new ArrayList<>();
if (input == null || input.length == 0 || k <= 0 || k > input.length) {
return result;
}
int start = 0, end = input.length - 1;
int index = partition(input, start, end);
while (index != k - 1) {
if (index > k - 1) {
end = index - 1;
} else {
start = index + 1;
}
index = partition(input, start, end);
}
for (int i = 0; i < k; i++) {
result.add(input[i]);
}
return result;
}
// 基于《算法（第4版）》的快速排序算法代码
private int partition(int[] a, int lo, int hi) {
if (lo == hi) {
return lo;
}
int i = lo, j = hi + 1;
int v = a[lo];
while (true) {
while (a[++i] < v) {
if (i == hi) {
break;
}
}
while (v < a[--j]) {
if (j == lo) {
break;
}
}
if (i >= j) {
break;
}
exch(a, i, j);
}
exch(a, lo, j);
return j;
}
private void exch(int[] a, int i, int j) {
int t = a[i];
a[i] = a[j];
a[j] = t;
}
}
复杂度分析
- 时间复杂度：O(n)。
- 空间复杂度：O(1)。
解法二：时间复杂度为 O(nlogk) 的算法，特别适合处理海量数据
import java.util.ArrayList;
import java.util.PriorityQueue;
public class Solution {
public ArrayList<Integer> GetLeastNumbers_Solution(int[] input, int k) {
ArrayList<Integer> result = new ArrayList<>();
if (input == null || input.length == 0 || k <= 0 || k > input.length) {
return result;
}
PriorityQueue<Integer> queue = new PriorityQueue<>();
for (int number : input) {
queue.add(number);
}
for (int i = 0; i < k; i++) {
result.add(queue.poll());
}
return result;
}
}
复杂度分析
- 时间复杂度：O(nlogk)。
- 空间复杂度：O(n)。
