LeetCode热题100之347：Top K Frequent Elements提交错误求助

我在解决LeetCode热题100中的347题Top K Frequent Elements时，本地PyCharm运行测试用例结果正确，但提交至LeetCode后被判错误。

我的代码 #

class Solution(object):
    def topKFrequent(self, nums, k):
        """
        :type nums: List[int]
        :type k: int
        :rtype: List[int]
        """
        '''counting keywords and their frequencies into a dict'''
        record = {}
        for num in nums:
            if num not in record:
                record[num] = 1
            else:
                record[num] += 1

        '''sort the dict according to the frequencies with reverse order'''
        topk = list(dict(sorted(record.items(), key=lambda items: items[1], reverse=True)))[:k]

        return topk


if __name__ == "__main__":
    sol = Solution()
    nums = [4,1,-1,2,-1,2,3]
    output = sol.topKFrequent(nums=nums, k=2)

问题原因 #

问题出在排序后转字典再提取key的步骤：

• 本地PyCharm大概率使用Python 3.7及以上版本，这类版本的字典会保留插入顺序，所以dict(sorted(...))能维持排序后的结果，转成列表取前k个key是正确的。
• 但LeetCode的运行环境可能使用Python 3.6或更早版本，这些版本的字典是无序的，转成字典后会直接丢失排序结果，最终取到的前k个元素自然不符合题目要求。

修正方案 #

跳过转字典的步骤，直接从排序后的元组列表中提取前k个元素的key：

class Solution(object):
    def topKFrequent(self, nums, k):
        record = {}
        # 简化计数逻辑
        for num in nums:
            record[num] = record.get(num, 0) + 1
        
        # 直接从排序结果中取前k个key
        topk = [item[0] for item in sorted(record.items(), key=lambda x: x[1], reverse=True)[:k]]
        return topk

更简洁的写法 #

可以用collections.Counter简化计数和取top k的逻辑：

from collections import Counter

class Solution(object):
    def topKFrequent(self, nums, k):
        count = Counter(nums)
        return [item[0] for item in count.most_common(k)]

内容的提问来源于stack exchange，提问作者missmango