面试题 17.14. 最小K个数

╰+攻爆jí腚メ 2022-09-10 03:18 98阅读 0赞

#### 2021-09-03 LeetCode每日一题 ####

链接：[https://leetcode-cn.com/problems/smallest-k-lcci/][https_leetcode-cn.com_problems_smallest-k-lcci]

标签：**数组、分治、快速选择、排序、堆**

> 题目

设计一个算法，找出数组中最小的k个数。以任意顺序返回这k个数均可。

示例：

输入： arr = [1,3,5,7,2,4,6,8], k = 4
    输出： [1,2,3,4]

提示：

*  0 <= len(arr) <= 100000
 *  0 <= k <= min(100000, len(arr))

> 分析

解法1：排序。

解法2：大顶堆。大顶堆就是根节点是最大的，左右子节点都比根节点小。正好可以用来求最小的k个数。初始化大顶堆容量为k，加入前k个数后，剩余的数加入时和堆顶元素比较，如果比堆顶元素小，则堆顶元素出堆，把这个数加入大顶堆重新排列，最后剩下的就是最小的k个数。从大到小排列。

Java自带的数据结构`PriorityQueue`默认是小顶堆，所以在初始化的时候需要指定排序函数。

解法3：小顶堆。根节点是最小的，不指定堆的容量，把数组的数全局放入堆中，取出前k个数即可。

注意`PriorityQueue`类的构造函数

PriorityQueue(int initialCapacity,
                         Comparator<? super E> comparator)
                         
    IllegalArgumentException - 如果 initialCapacity小于1

而此题k是可能为0的。

> 编码

**解法1：排序**

class Solution { 
        public int[] smallestK(int[] arr, int k) { 
            Arrays.sort(arr);
            int[] res = new int[k];
            for (int i = 0; i < k; i++) { 
                res[i] = arr[i];
            }
    
            return res;
        }
    }

![请添加图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA56eD5aS05ZOl57yW56iL_size_20_color_FFFFFF_t_70_g_se_x_16]

**解法2：大顶堆**

class Solution { 
        public int[] smallestK(int[] arr, int k) { 
            int[] res = new int[k];
            if (k == 0) { 
                return res;
            }
            PriorityQueue<Integer> queue = new PriorityQueue<>(k, (a, b) -> { 
                return b - a;
            });
    
            for (int num : arr) { 
                if (queue.size() < k) { 
                    queue.offer(num);
                } else if (queue.peek() > num) { 
                    queue.poll();
                    queue.offer(num);
                }
            }
            
            for (int i = 0; i < k; i++) { 
                res[i] = queue.poll();
            }
            return res;
        }
    }

![请添加图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA56eD5aS05ZOl57yW56iL_size_20_color_FFFFFF_t_70_g_se_x_16 1]

**解法3：小顶堆**

class Solution { 
        public int[] smallestK(int[] arr, int k) { 
            int[] res = new int[k];
            if (k == 0) { 
                return res;
            }
            PriorityQueue<Integer> queue = new PriorityQueue<>(k);
    
            for (int num : arr) { 
                queue.offer(num);
            }
            
            for (int i = 0; i < k; i++) { 
                res[i] = queue.poll();
            }
            return res;
        }
    }

![请添加图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA56eD5aS05ZOl57yW56iL_size_20_color_FFFFFF_t_70_g_se_x_16 2]

[https_leetcode-cn.com_problems_smallest-k-lcci]: https://leetcode-cn.com/problems/smallest-k-lcci/
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA56eD5aS05ZOl57yW56iL_size_20_color_FFFFFF_t_70_g_se_x_16]: /images/20220829/d0f2e7800981433983ebb90d76299526.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA56eD5aS05ZOl57yW56iL_size_20_color_FFFFFF_t_70_g_se_x_16 1]: /images/20220829/1ef54fff180246498d667a102257828e.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA56eD5aS05ZOl57yW56iL_size_20_color_FFFFFF_t_70_g_se_x_16 2]: /images/20220829/ecdf1fd91e4648659ab23f524c8a91bf.png