gpt4 book ai didi

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

转载 作者:大佬之路 更新时间:2024-01-31 14:20:13 27 4
gpt4 key购买 nike

题目地址: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 弟弟快看-教程,程序员编程资料站,版权归原作者所有

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

27 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com