当前位置 博文首页 > 数据结构和算法：剑指 Offer-最小的k个数
截止到目前我已经写了 500多道算法题，其中部分已经整理成了pdf文档，目前总共有1000多页（并且还会不断的增加），大家可以免费下载
下载链接：https://pan.baidu.com/s/1hjwK0ZeRxYGB8lIkbKuQgQ
提取码：6666
public int[] getLeastNumbers(int[] arr, int k) {
//先排序，然后选择前k个即可
Arrays.sort(arr);
int[] res = new int[k];
for (int i = 0; i < k; ++i) {
res[i] = arr[i];
}
return res;
}
关于堆不熟悉的可以看下《378，数据结构-7,堆》，堆分为最大堆和最小堆，最大堆的堆顶元素是堆中最大的，最小堆的堆顶元素是堆中最小的。这里可以使用最大堆，我们把堆看做是一个容器，最大只能容纳k个元素，具体实现如下：
遍历数组中的每一个元素，
原理比较简单，我们来看下代码
public int[] getLeastNumbers(int[] arr, int k) {
//加个边界条件的判断
if (k == 0) {
return new int[0];
}
//创建最大堆
PriorityQueue<Integer> queue = new PriorityQueue<>((num1, num2) -> num2 - num1);
//先在堆中放数组的前k个元素
for (int i = 0; i < k; ++i) {
queue.offer(arr[i]);
}
//因为是最大堆，也就是堆顶的元素是堆中最大的，遍历数组后面元素的时候，
//如果当前元素比堆顶元素大，就把堆顶元素给移除，然后再把当前元素放到堆中，
for (int i = k; i < arr.length; ++i) {
if (queue.peek() > arr[i]) {
queue.poll();
queue.offer(arr[i]);
}
}
//最后再把堆中元素转化为数组
int[] res = new int[k];
for (int i = 0; i < k; ++i) {
res[i] = queue.poll();
}
return res;
}
如果对堆不熟悉，还可以换种方式，使用TreeMap，原理都是一样的。
public int[] getLeastNumbers(int[] arr, int k) {
//加个边界条件的判断
if (k == 0) {
return new int[0];
}
//map中key存放数组中元素，value存放这个元素的个数
TreeMap<Integer, Integer> map = new TreeMap<>();
int count = 0;
for (int i = 0; i < arr.length; i++) {
//map中先存放k个元素，之后map中元素始终维持在k个
if (count < k) {
map.put(arr[i], map.getOrDefault(arr[i], 0) + 1);
count++;
continue;
}
Map.Entry<Integer, Integer> entry = map.lastEntry();
//从第k+1个元素开始，每次存放的时候都要和map中最大的那个比较，如果比map中最大的小，
//就把map中最大的给移除，然后把当前元素加入到map中
if (entry.getKey() > arr[i]) {
//移除map中最大的元素，如果只有一个直接移除。如果有多个（数组中会有重复的元素），移除一个就行
if (entry.getValue() == 1) {
map.pollLastEntry();
} else {
map.put(entry.getKey(), entry.getValue() - 1);
}
//把当前元素加入到map中
map.put(arr[i], map.getOrDefault(arr[i], 0) + 1);
}
}
//把map中key存放到集合list中
int[] res = new int[k];
int index = 0;
for (Map.Entry<Integer, Integer> entry : map.entrySet()) {
int keyCount = entry.getValue();
while (keyCount-- > 0) {
res[index++] = entry.getKey();
}
}
return res;
}
参考：《104，排序-快速排序》
视频链接
public int[] getLeastNumbers(int[] arr, int k) {
int[] res = new int[k];
quickSort(arr, res, k, 0, arr.length - 1);
return res;
}
private void quickSort(int[] arr, int[] res, int k, int left, int right) {
//快排的实现方式有多种，我们选择了其中的一种
int start = left;
int end = right;
while (left < right) {
while (left < right && arr[right] >= arr[start]) {
right--;
}
while (left < right && arr[left] <= arr[start]) {
left++;
}
swap(arr, left, right);
}
swap(arr, left, start);
//注意这里，start是数组中元素的下标。在start之前的元素都是比start指向的元素小，
//后面的都是比他大。如果k==start，正好start之前的k个元素是我们要找的，也就是
//数组中最小的k个，如果k>start，说明前k个元素不够，我们还要往后再找找。如果
//k<start，说明前k个足够了，我们只需要在start之前找k个即可。
if (left > k) {
quickSort(arr, res, k, start, left - 1);
} else if (left < k) {
quickSort(arr, res, k, left + 1, end);
} else {
//取前面的k个即可
for (int m = 0; m < k; ++m) {
res[m] = arr[m];
}
}
}
//交换数组中两个元素的值
private void swap(int[] arr, int i, int j) {
if (i == j)
return;
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
