Algorithms will always matter.
的确，无论现在的计算能力如何提高，人们总会发现立即会有更多的数据需要处理。
依然是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.
显然，扫描数组，使用元素值作为hash-key，保存每个数字出现的次数，变身为top-k 问题。
Top K Problem
对于top k 问题是利用堆排序，首先建立最大堆，交换堆顶元素与最后一个有序的元素，调整最大堆至所有元素有序。
由于只需要K个元素有序，所以只需进行k次shift-down调整即可。
代码实现
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]
复杂度分析
首先，建堆需要O(N)时间， 然后每次调整需要logN，共发生k次调整，总时间为O(N+K*logN)。
更优雅的做法
我们的实现仍然缺少map的统计，代码已经比较臃肿。是否有更优雅的做法呢？答案是利用python提供内置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的优雅了吗？
后记
top k问题在编程之美这本书中被挖掘到了不能再美。不过，还记得文章开始的引子吗？ 是的，如果数据变大，所有数据分布在不同的机器集群上，如何获得所有集群上的top-k呢？
