面试题17.14.最小K个数
难度：中等
题目：
设计一个算法，找出数组中最小的k个数。以任意顺序返回这k个数均可。
提示：
- 0 <= len(arr) <= 100000
- 0 <= k <= min(100000, len(arr))
示例：
输入： arr = [1,3,5,7,2,4,6,8], k = 4 输出： [1,2,3,4]
分析
这道题之所以定义为堆排序类型题，就是因为可以任意顺序返回。 这里推排序有两种思路：
- 小根堆：每次获取的数据都无脑入堆，然后最终将前K个数字返回
- 大根堆：仅维护K个长度的堆，由于python没有，需要入赋值，如果当前的数大于heap[0]，则堆顶出堆，当前数入堆，最终返回。
至于 return sorted(arr)[:k] 的写法，面试时候不怕被打，你就这么写。
解题：
import heapq class Solution: def smallestK(self, arr, k): if k == 0: return [] hq = [] for i in arr: if len(hq) < k: heapq.heappush(hq, -i) else: if hq[0] < -i: heapq.heappop(hq) heapq.heappush(hq, -i) return [-i for i in hq]
347.前K个高频元素
难度：中等
题目：
给你一个整数数组 nums 和一个整数 k ，请你返回其中出现频率前 k 高的元素。你可以按 任意顺序 返回答案。
提示：
- 1 <= nums.length <= 10 ^ 5
- k 的取值范围是 [1, 数组中不相同的元素的个数]
- 题目数据保证答案唯一，换句话说，数组中前 k 个高频元素的集合是唯一的
示例：
示例 1: 输入: nums = [1,1,1,2,2,3], k = 2 输出: [1,2] 示例 2: 输入: nums = [1], k = 1 输出: [1]
分析
遇到重复数字求频率，首先要想到Counter计数原则，将当前的数组转换为hash表 num:frequency 的类型然后再做操作。
即： dic = collections.Counter(nums)
分享两种方法（虽然面试官更希望你写第二种，但如果同时写出第一种，能展示出你对基础模块的掌握度）：
1.sorted方法
使用sorted自带的排序和列表切片后返回，可以压缩到一行代码
2.堆排序
这道题提及了任意顺序返回均可，那就可以通过使用堆的方法来解决了。这道题使用小根堆很方便。
类似的题目有：
sorted解题：
from collections import Counter class Solution: def topKFrequent(self, nums, k): return [x[0] for x in sorted(Counter(nums).items(),key = lambda x: x[1],reverse=True)[:k]]
堆排序解题：
from collections import Counter import heapq class Solution: def topKFrequent(self, nums, k): dic = Counter(nums) hp = [] for num, req in dic.items(): if len(hp) < k: heapq.heappush(hp, (req, num)) else: if req > hp[0][0]: heapq.heappop(hp) heapq.heappush(hp, (req, num)) return [x[1] for x in hp]
973.最接近原点的K个点
难度：中等
题目：
我们有一个由平面上的点组成的列表 points。需要从中找出 K 个距离原点 (0, 0) 最近的点。
（这里，平面上两点之间的距离是欧几里德距离。）
你可以按任何顺序返回答案。除了点坐标的顺序之外，答案确保是唯一的。
提示：
- 1 <= K <= points.length <= 10000
- -10000 < points[i][0] < 10000
- -10000 < points[i][1] < 10000
示例：
示例 1： 输入：points = [[1,3],[-2,2]], K = 1 输出：[[-2,2]] 解释： (1, 3) 和原点之间的距离为 sqrt(10)， (-2, 2) 和原点之间的距离为 sqrt(8)， 由于 sqrt(8) < sqrt(10)，(-2, 2) 离原点更近。 我们只需要距离原点最近的 K = 1 个点，所以答案就是 [[-2,2]]。 示例 2： 输入：points = [[3,3],[5,-1],[-2,4]], K = 2 输出：[[3,3],[-2,4]] （答案 [[-2,4],[3,3]] 也会被接受。）
分析
遇到求前K的题目，内置的sorted和堆排序无脑安排上就对了，类似的题目有：
这道题同样的，我们使用堆排序(大根堆)来完成解题，维护一个K大的堆，然后每次判断距离是否比堆顶的数字大。
如果比堆顶数字大，弹出堆顶，将当前距离及点信息以列表方式入堆即可。
解题：
import heapq class Solution: def kClosest(self, points, k): hp = [] for point in points: distance = sum(map(lambda x: abs(x ** 2), point)) if len(hp) < k: heapq.heappush(hp, [-distance, point]) else: if -distance > hp[0][0]: heapq.heappop(hp) heapq.heappush(hp, [-distance, point]) return [point for distance, point in hp]
