Algorithms will always matter.
的確，無論現(xiàn)在的計(jì)算能力如何提高调缨，人們總會發(fā)現(xiàn)立即會有更多的數(shù)據(jù)需要處理好芭。
依然是leetcode上的題目：
Given a non-empty array of integers, return the k most frequent elements.
For example,Given [1,1,1,2,2,3]
and k = 2, return [1,2]
.
Note: **
You may assume k is always valid, 1 ≤ k ≤ number of unique elements.
Your algorithm's time complexity must be better than O(n log n), where n is the array's size.
顯然，掃描數(shù)組鸥滨，使用元素值作為hash-key，保存每個數(shù)字出現(xiàn)的次數(shù)谤祖，變身為top-k 問題婿滓。
Top K Problem
對于top k 問題是利用堆排序，首先建立最大堆泊脐，交換堆頂元素與最后一個有序的元素空幻，調(diào)整最大堆至所有元素有序。
由于只需要K個元素有序容客，所以只需進(jìn)行k次shift-down調(diào)整即可秕铛。
代碼實(shí)現(xiàn)
def top_k(nums, k):
length = len(nums)
def shift_down(start, end):
root = start
while True:
child = 2 * root + 1
if child > end:
break;
if child + 1 <= end and nums[child] < nums[child + 1]:
child += 1
if nums[root] < nums[child]:
nums[root], nums[child] = nums[child],nums[root]
root = child
else:
break
for start in xrange((length - 2) // 2, -1, -1):
shift_down(start, length - 1)
for end in xrange(length - 1, length - k - 1, -1):
nums[0], nums[end] = nums[end], nums[0]
shift_down(0, end - 1)
return nums[-1 : length - k - 1 : -1]
復(fù)雜度分析
首先，建堆需要O(N)時間缩挑， 然后每次調(diào)整需要logN但两，共發(fā)生k次調(diào)整，總時間為O(N+K*logN)供置。
更優(yōu)雅的做法
我們的實(shí)現(xiàn)仍然缺少map的統(tǒng)計(jì)谨湘，代碼已經(jīng)比較臃腫。是否有更優(yōu)雅的做法呢芥丧？答案是利用python提供內(nèi)置Counter類庫紧阔。
def topKFrequent(self, nums, k):
cnt = Counter()
for i in nums:
cnt[i] += 1
return [ x for x,y in cnt.most_common(k) ]
怎樣，寥寥4行代碼之間是否讓你感到python的優(yōu)雅了嗎续担？
后記
top k問題在編程之美這本書中被挖掘到了不能再美擅耽。不過，還記得文章開始的引子嗎物遇？ 是的乖仇，如果數(shù)據(jù)變大憾儒，所有數(shù)據(jù)分布在不同的機(jī)器集群上，如何獲得所有集群上的top-k呢乃沙？
