347.Top K Frequent Elements

Tags: [heap], [map], [sort], [bucket_sort]

Link: https://leetcode.com/problems/top-k-frequent-elements/#/description

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.

Solution: bucket sort

class Solution(object):
    def topKFrequent(self, nums, k):
        """
        :type nums: List[int]
        :type k: int
        :rtype: List[int]
        """
        if not nums or not k:
            return []

        counting_map = {}
        for num in nums:
            if num not in counting_map:
                counting_map[num] = 1
            else:
                counting_map[num] += 1

        min_frequence = len(nums) + 1
        max_frequence = 0

        for num in counting_map:
            min_frequence = min(min_frequence, counting_map[num])
            max_frequence = max(max_frequence, counting_map[num])

        # bucket sort
        buckets = [[] for _ in xrange(max_frequence - min_frequence + 1)]

        for num in counting_map:
            frequence = counting_map[num]
            buckets[frequence - min_frequence].append(num)

        result = []
        for i in xrange(len(buckets) - 1, -1, -1):
            if len(result) == k:
                break

            if buckets[i]:
                result += buckets[i]

        return result

Revelation:

• It is reasonable that we use bucket sort here, because we know the max_frequence <= n, n is the number of elements. So the number of buckets should not be very big.
• If we have start and end, the number of elements in the range[start, end] is equal to (end - start + 1).
• Bucket sort, each bucket contains a list, using this to deal with duplicate elements.

Note:

• Time complexity = O(n), n is the number of elements in the given nums.

Solution: heap, map

import heapq

class Solution(object):

    class Num(object):
        def __init__(self, num, frequence):
            self.num = num
            self.frequence = frequence

        def __cmp__(self, other):
            if not isinstance(other, self.__class__):
                raise ValueError('other type is different from the current obj')

            return -(self.frequence - other.frequence)

    def topKFrequent(self, nums, k):
        """
        :type nums: List[int]
        :type k: int
        :rtype: List[int]
        """
        if not nums or not k:
            return []

        counting_map = {}
        for num in nums:
            if num not in counting_map:
                counting_map[num] = 1
            else:
                counting_map[num] += 1

        max_heap = []
        for num in counting_map:
            max_heap.append(self.Num(num, counting_map[num]))

        heapq.heapify(max_heap)

        result = []
        while max_heap and len(result) < k:
            num = heapq.heappop(max_heap)
            result.append(num.num)

        return result

Note:

• Time complexity = O(klgn), n is the number of elements of nums.