347. Top K Frequent Elements 前 K 个高频元素

题目地址：https://leetcode.com/problems/top-k-frequent-elements/description/

题目描述

Given a non-empty array of integers, return the k most frequent elements.

Forexample,

Given [1,1,1,2,2,3] and k = 2, return [1,2].

Note:

1、 Youmayassumekisalwaysvalid,1≤k≤numberofuniqueelements.；
2、 Youralgorithm'stimecomplexitymustbebetterthanO(nlogn),wherenisthearray'ssize.；

解题方法

把出现次数最大的前k个数输出。

解题方法

字典

这个题要求时间复杂度是O(nlogn)，就可以按照出现的次数先排个序，然后找到出现最多的k个就好。Counter类有most_common()函数，能按出现的次数进行排序。返回的是个列表，列表中每个元素都是一个元组，元组的第一个元素是数字，第二个数字是出现的次数。

from collections import Counter
class Solution(object):
    def topKFrequent(self, nums, k):
        """
        :type nums: List[int]
        :type k: int
        :rtype: List[int]
        """
        counter = Counter(nums).most_common()
        return [counter[i][0] for i in range(k)]

1 2 3 4 5 6 7 8 9 10

优先级队列

使用优先级队列来让出现次数多的优先弹出来，当然需要字典统计次数。

class Solution {
public:
    vector<int> topKFrequent(vector<int>& nums, int k) {
        map<int, int> m;
        for (int n : nums) m[n] ++;
        priority_queue<pair<int, int>> p;
        for (auto a : m)
            p.push({a.second, a.first});
        vector<int> res;
        for (int i = 0; i < k; i++) {
            res.push_back(p.top().second); p.pop();
        }
        return res;
    }
};

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15

DDKK.COM 弟弟快看-教程，程序员编程资料站，版权归原作者所有

本文经作者：负雪明烛 授权发布，任何组织或个人未经作者授权不得转发