說一道排序題
這是崔斯特的第七十六篇原創文章
很經典的排序問題 (๑• . •๑)
先看題目,“前K個高頻元素”
給定一個非空的整數陣列,返回其中出現頻率前 k 高的元素。
示例 1:
輸入: nums = [1,1,1,2,2,3], k = 2 輸出: [1,2]
示例 2:
輸入: nums = [1], k = 1 輸出: [1]
簡單解法
這題很簡單,兩步:
- 用字典儲存數字及其出現的對應頻率
- 排序
那麼第一步就不用說了,很簡單
m = dict() for num in nums: if num in m: m[num] += 1 else: m[num] = 1
有趣的就在第二步,排序。很多人都是使用內建庫 sorted
class Solution(object): def topKFrequent(self, nums, k): """ :type nums: List[int] :type k: int :rtype: List[int] """ m = dict() for num in nums: if num in m: m[num] += 1 else: m[num] = 1 output = sorted(m.items(), key=lambda e: e[1], reverse=True) final = [] for i in range(k): final.append(output[i][0]) return final
最簡潔的程式碼是直接使用Python內建的 collections
class Solution(object): def topKFrequent(self, nums, k): """ :type nums: List[int] :type k: int :rtype: List[int] """ import collections counter = collections.Counter(nums) return [item[0] for item in counter.most_common(k)]
這真是是我們想要的嗎?並不是。我們的目標是不使用任何內建庫。
sorted原理
關於Python的sorted排序演算法,這篇文章講的比較詳細: ofollow,noindex">python sort函式內部實現原理 ,說到Python使用的是著名的 Timesort
演算法。
Timsort
是結合了合併排序(merge sort)和插入排序(insertion sort)而得出的排序演算法,它在現實中有很好的效率。
Tim Peters在2002年設計了該演算法並在Python中使用(TimSort 是 Python 中 list.sort 的預設實現)。該演算法找到資料中已經排好序的塊-分割槽,每一個分割槽叫一個run,然後按規則合併這些run。Pyhton自從2.3版以來一直採用Timsort演算法排序,現在Java SE7和Android也採用Timsort演算法對陣列排序。
如果想自己用Python來寫一個排序演算法,完成本題要求該如何寫?也就是對這個字典進行排序, {5: 1, 1: 3, 4: 1, 2: 2, 3: 1}
,有什麼好辦法。
思路可以是兩個指標遍歷字典,如果左邊大於右邊,則替換位置。
更好的方法
class Solution(object): def topKFrequent(self, nums, k): """ :type nums: List[int] :type k: int :rtype: List[int] """ m = dict() for num in nums: if num in m: m[num] += 1 else: m[num] = 1 bucket = [[] for _ in range(len(nums) + 1)] for key, value in m.items(): bucket[value].append(key) result = [] for i in range(len(nums), 0, -1): for n in bucket[i]: result.append(n) if len(result) == k: return result return result
很巧妙的使用列表的索引來儲存value。
此時bucket值是 [[], [5, 4, 3], [2], [1], [], [], [], [], []]
,索引即出現次數。
此解法用時72ms,戰勝 50.84 % 的 python3 提交記錄。但是看了排在前面的演算法,都是使用的Python內建的 collections
。
如果是你,會用什麼方法呢?