四种方法花式吊打面试题目——最小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中当前数字对应个数+1 if (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; } }