<LeetCode-python3>前K个高频元素

给定一个非空的整数数组,返回其中出现频率前 k 高的元素。

例如,

给定数组 [1,1,1,2,2,3] , 和 k = 2,返回 [1,2]。

注意:

你可以假设给定的 k 总是合理的,1 ≤ k ≤ 数组中不相同的元素的个数。
你的算法的时间复杂度必须优于 O(n log n) , n 是数组的大小。

解题思路:
这里我们直接使用python内置库collections的Count方法,它可以对一个数组进行归类计数,和mapreduces的map函数类似,但是Count是根据元素出现在原始数组里的位置进行排序的,所以我们还需要用到一个most_commen(k)函数,它可以输出数量最多的k个元素。
当然,要是不想使用内置库的话,可以使用字典遍历计数,但思路都是一样的。
代码如下:

def topKFrequent(self, nums, k):
    """
    :type nums: List[int]
    :type k: int
    :rtype: List[int]
    """
    counter = collections.Counter(nums)
    return [item[0] for item in counter.most_common(k)]

另外LeetCode的时间记录有时会很迷,同一样的代码运行三次,得到的时间不一样。可能是这题的测试用例比较少,总共几十毫秒的运行时间就不是那么准确了,当数据多了后应该就能显示出差距了。

©著作权归作者所有,转载或内容合作请联系作者
【社区内容提示】社区部分内容疑似由AI辅助生成,浏览时请结合常识与多方信息审慎甄别。
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。

相关阅读更多精彩内容

友情链接更多精彩内容