Top K most frequent element

一个题，问了所有的做法。一个sorted list，找popular value（定义为出现次数 > N／4），然后问了我会拿什么test case去test，然后让我问问题。

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(nlogn), where n is the array's size.

Method 1 Hashmap + List(runtime: nlog(n))

• iterate the array and store each element's frequency into a hashmap. O(n).
• reversely sort all the key value pairs from the hashmap into an array. O(nlog(n)
• return the first k elements from the resulting array. O(k)

def topKFrequent(self, nums, k):
    hm = {}
    for num in nums:
        hm[num] = hm[num] + 1 if num in hm else 1
    pairs = sorted(hm.items(), key=lambda x:x[1], reverse=True)
    return [pair[0] for pair in pairs[:k]]

Method 2 Hashmap + (min)Heap(runtime: nlog(k))

• iterate the array and store each element's frequency into a hashmap. O(n)
• iterate the key value pairs from the map and insert each into the heap by the value. (nlog(k))
  • After each insert, pop the root from the heap if size of heap is > k.
• return all the keys from the heap. (k)

import heapq
def topKFrequent(self, nums, k):
    hm, heap = {}, []
    for num in nums:
        hm[num] = hm[num] + 1 if num in hm else 1
    for num, count in hm.iteritems():
        heapq.heappush(heap,(count, num))
        if len(heap) > k:
            heapq.heappop(heap)
    return [i[1] for i in heap]

Method 3 Two Hashmaps + iterate all possible frequencies (runtime: n):

def topKFrequent(self, nums, k):
    hs, frq = {}, {}
    output = []

    for num in nums:
        if num not in hs:
            hs[num] = 1
        else:
            hs[num] += 1

    for num, count in hs.iteritems():
        if count not in frq:
            frq[count] = [num]
        else:
            frq[count].append(num)

    for x in xrange(len(nums), 0, -1):
        if x in frq:
            output.extend(frq[x])

    return output[:k]

Testing:

1. Is K guarrenteed to be 1<=k<=len(nums)?
2. Is nums guarrenteed to be non-empty?
3. topKFrequent([1],1) when nums has 1 element
4. topKFrequent([3,4,5,1,0,1,3, 5) when k is the amount of all distinct elements
5. topKFrequent([3,5,0,2,0], 1) when k is the most frequent element
6. ASK WHAT IF K=1, NUMS=[1,2,3], WHAT SHOULD RETURN?