思路:
题目的主要信息:
- 对于一个给定无序数组,返回最小的k个元素
- k和数组有特殊情况需要单独讨论,且数组最大10000
方法一:堆排序
具体做法:
使用Java自带的PriorityQueue模拟一个大顶堆,堆的大小限定在最大k:遍历数组,前k个元素直接入堆,后续元素如果比堆顶元素大,则弹出堆顶,再入堆。
最后将所有堆中的元素加入到ArrayList即可返回。
import java.util.ArrayList; import java.util.*; public class Solution { public ArrayList<Integer> GetLeastNumbers_Solution(int [] input, int k) { ArrayList<Integer> res = new ArrayList<Integer>(); if (k == 0 || input.length == 0) { return res; } // 大顶堆 Queue<Integer> pq = new PriorityQueue<>((v1, v2) -> v2 - v1); for (int num: input) { if (pq.size() < k) { pq.offer(num); } else if (num < pq.peek()) { pq.poll(); pq.offer(num); } } // 返回堆中的元素 for(int num: pq) { res.add(num); } return res; } }
复杂度分析:
- 时间复杂度:,n个元素,每次维护堆需要
- 空间复杂度:,堆空间最大为k
方法二:直接计数法
具体做法:
因为数据量是限定好的,不超过10000,所以我们可以用大小为10001的数组记录0-10000这些数字在数组中出现的次数,然后遍历计数数组counter,取前面k个存在的数字,如果某个数字出现多次,也需要让它在结果中多次出现,并使k相应往前。
import java.util.ArrayList; import java.util.*; public class Solution { public ArrayList<Integer> GetLeastNumbers_Solution(int [] input, int k) { ArrayList<Integer> res = new ArrayList<Integer>(); if (k == 0 || input.length == 0) { return res; } // 统计每个数字出现的次数 int[] counter = new int[10001]; for (int num: input) { counter[num]++; } // 根据counter数组从头找出k个数作为返回结果 for (int num = 0; num < counter.length; num++) { while (counter[num]-- > 0 && res.size() < k) { res.add(num); } if (res.size() == k) { break; } } return res; } }
复杂度分析:
- 时间复杂度:,两次遍历都是单循环
- 空间复杂度:,辅助数组记录每个数组出现的次数