K个数、K个点、K个元素，3K堆排序，类比三解题！
2021-06-29 本文已影响0人
清风Python
面试题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]
欢迎关注我的公众号: 清风Python，带你每日学习Python算法刷题的同时，了解更多python小知识。
我的个人博客：https://qingfengpython.cn
