四种方法花式吊打面试题目——最小k个数"/>
四种方法花式吊打面试题目——最小k个数
最小K个数
算法题目:
输入一个整数数组arr,找出其中最小的k个数。
思路
比较直观的想法就是将整个数组排序,然后输出前K小的数,所以我们使用目前最高效的排序算法,快排来解决问题。所以所需的时间复杂度O(nlogn)。但是由于取前K个数所以快排不用完全执行。
快排思想
直接通过快排切分好第K小的数(下标k-1)
大根堆(前K小)/小根堆(前K大)
- 因为java中有现成的PriorityQueue,实现起来简单O(NlogK)
是因为求前k小,所以用一个容量为K的大根堆,每次poll出最大的数,那堆中保留就是前K小
这个方法虽然比较慢(比快排)但是由于有现成的 PriorityQueue(默认小根堆)
二叉搜索树
- 好处是求得的前K大的数字是有序的
- 因为存在重复数字,所以使用TreeMap而不是TreeSet
- Tree的key是数字,value是该数字的个数
我们遍历数组中的数组,维护一个数字总个数为K的TreeMap
- 若目前map中的数字个数小于K,则将map中当前数字对应的个数+1
- 否则,判断当前数字与map中最大数字的大小关系
- 大于等于最大数字则直接跳过
- 否则将map中对应数字的个数+1,并将map中最大数字对应的个数-1
当有数据范围时直接计数排序
代码实现
快排思想
class Solution {public int[] getLeastNumbers(int[] arr, int k) {if (k == 0 || arr.length == 0) {return new int[0];}// 最后一个参数表示我们要找的是下标为k-1的数return quickSearch(arr, 0, arr.length - 1, k - 1);}private int[] quickSearch(int[] nums, int lo, int hi, int k) {// 每快排切分1次,找到排序后下标为j的元素,如果j恰好等于k就返回j以及j左边所有的数;int j = partition(nums, lo, hi);if (j == k) {return Arrays.copyOf(nums, j + 1);}// 否则根据下标j与k的大小关系来决定继续切分左段还是右段。return j > k? quickSearch(nums, lo, j - 1, k): quickSearch(nums, j + 1, hi, k);}// 快排切分,返回下标j,使得比nums[j]小的数都在j的左边,比nums[j]大的数都在j的右边。private int partition(int[] nums, int lo, int hi) {int v = nums[lo];int i = lo, j = hi + 1;while (true) {while (++i <= hi && nums[i] < v);while (--j >= lo && nums[j] > v);if (i >= j) {break;}int t = nums[j];nums[j] = nums[i];nums[i] = t;}nums[lo] = nums[j];nums[j] = v;return j;}
}
大根堆
// 保持堆的大小为K,然后遍历数组中的数字,遍历的时候做如下判断:
// 1. 若目前堆的大小小于K,将当前数字放入堆中。
// 2. 否则判断当前数字与大根堆堆顶元素的大小关系,如果当前数字比大根堆堆顶还大,这个数就直接跳过;
// 反之如果当前数字比大根堆堆顶小,先poll掉堆顶,再将该数字放入堆中。
class Solution {public int[] getLeastNumbers(int[] arr, int k) {if (k == 0 || arr.length == 0) {return new int[0];}// 默认是小根堆,实现大根堆需要重写一下比较器。Queue<Integer> pq = new PriorityQueue<>((v1, v2) -> v2 - v1);for (int num: arr) {if (pq.size() < k) {pq.offer(num);} else if (num < pq.peek()) {pq.poll();pq.offer(num);}}// 返回堆中的元素int[] res = new int[pq.size()];int idx = 0;for(int num: pq) {res[idx++] = num;}return res;}
}
二叉搜索树
class Solution {public int[] getLeastNumbers(int[] arr, int k) {if (k == 0 || arr.length == 0) {return new int[0];}// TreeMap的key是数字, value是该数字的个数。// cnt表示当前map总共存了多少个数字。TreeMap<Integer, Integer> map = new TreeMap<>();int cnt = 0;for (int num: arr) {// 1. 遍历数组,若当前map中的数字个数小于k,则map中当前数字对应个数+1if (cnt < k) {map.put(num, map.getOrDefault(num, 0) + 1);cnt++;continue;} // 2. 否则,取出map中最大的Key(即最大的数字), 判断当前数字与map中最大数字的大小关系:// 若当前数字比map中最大的数字还大,就直接忽略;// 若当前数字比map中最大的数字小,则将当前数字加入map中,并将map中的最大数字的个数-1。Map.Entry<Integer, Integer> entry = map.lastEntry();if (entry.getKey() > num) {map.put(num, map.getOrDefault(num, 0) + 1);if (entry.getValue() == 1) {map.pollLastEntry();} else {map.put(entry.getKey(), entry.getValue() - 1);}}}// 最后返回map中的元素int[] res = new int[k];int idx = 0;for (Map.Entry<Integer, Integer> entry: map.entrySet()) {int freq = entry.getValue();while (freq-- > 0) {res[idx++] = entry.getKey();}}return res;}
}
计数排序(有数据范围)
class Solution {public int[] getLeastNumbers(int[] arr, int k) {if (k == 0 || arr.length == 0) {return new int[0];}// 统计每个数字出现的次数int[] counter = new int[10001];for (int num: arr) {counter[num]++;}// 根据counter数组从头找出k个数作为返回结果int[] res = new int[k];int idx = 0;for (int num = 0; num < counter.length; num++) {while (counter[num]-- > 0 && idx < k) {res[idx++] = num;}if (idx == k) {break;}}return res;}
}
更多推荐
四种方法花式吊打面试题目——最小k个数
发布评论