面試題17.14.最小K個數(shù)
難度：中等
題目：
設(shè)計一個算法言缤，找出數(shù)組中最小的k個數(shù)。以任意順序返回這k個數(shù)均可禁灼。
提示：
- 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]
分析
這道題之所以定義為堆排序類型題管挟，就是因為可以任意順序返回。 這里推排序有兩種思路：
- 小根堆：每次獲取的數(shù)據(jù)都無腦入堆弄捕，然后最終將前K個數(shù)字返回
- 大根堆：僅維護K個長度的堆僻孝，由于python沒有，需要入賦值守谓，如果當前的數(shù)大于heap[0]皮璧，則堆頂出堆，當前數(shù)入堆分飞，最終返回睹限。
至于 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個高頻元素
難度：中等
題目：
給你一個整數(shù)數(shù)組 nums 和一個整數(shù) k 叨恨，請你返回其中出現(xiàn)頻率前 k 高的元素柳刮。你可以按 任意順序 返回答案。
提示：
- 1 <= nums.length <= 10 ^ 5
- k 的取值范圍是 [1, 數(shù)組中不相同的元素的個數(shù)]
- 題目數(shù)據(jù)保證答案唯一秉颗，換句話說痢毒，數(shù)組中前 k 個高頻元素的集合是唯一的
示例：
示例 1:
輸入: nums = [1,1,1,2,2,3], k = 2
輸出: [1,2]
示例 2:
輸入: nums = [1], k = 1
輸出: [1]
分析
遇到重復數(shù)字求頻率蚕甥，首先要想到Counter計數(shù)原則哪替，將當前的數(shù)組轉(zhuǎn)換為hash表 num:frequency 的類型然后再做操作。
即： dic = collections.Counter(nums)
分享兩種方法（雖然面試官更希望你寫第二種菇怀，但如果同時寫出第一種凭舶，能展示出你對基礎(chǔ)模塊的掌握度）：
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的題目还棱，內(nèi)置的sorted和堆排序無腦安排上就對了芦昔，類似的題目有：
這道題同樣的，我們使用堆排序(大根堆)來完成解題咕缎，維護一個K大的堆，然后每次判斷距離是否比堆頂?shù)臄?shù)字大焙蹭。
如果比堆頂數(shù)字大嫂伞，彈出堆頂，將當前距離及點信息以列表方式入堆即可帖努。
解題：
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]
歡迎關(guān)注我的公眾號: 清風Python拼余，帶你每日學習Python算法刷題的同時，了解更多python小知識匙监。
我的個人博客：https://qingfengpython.cn
