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

okokabcd 2023-03-28 原文

一、题目大意

https://leetcode.cn/problems/top-k-frequent-elements

给你一个整数数组 nums 和一个整数 k ，请你返回其中出现频率前 k 高的元素。你可以按任意顺序返回答案。
示例 1:

输入: nums = [1,1,1,2,2,3], k = 2
输出: [1,2]

示例 2:

输入: nums = [1], k = 1
输出: [1]

提示：

1 <= nums.length <= 105
k 的取值范围是 [1, 数组中不相同的元素的个数]
题目数据保证答案唯一，换句话说，数组中前 k 个高频元素的集合是唯一的

进阶：你所设计算法的时间复杂度必须优于 O(n log n) ，其中 n 是数组大小。

二、解题思路

题意：
给定一个数组，统计前k个高频的数字，顺序任意。
思路：
用桶排序来解决这个问题。使用哈希表统计频率，统计完成后创建一个数组，将频率作为数组下标，对于出现频率不同的数字集合，存入对应的数组下标即可。
实现：
使用HashMap来做，key为值，value为出现的频数

输入：nums:[1,1,1,1,2,2,3,4]  k:2

第一步：统计数值的频数，用map<Integer, Integer>存储
数值：1 2 3 4
频数：4 2 1 1

第二步：以频数构造桶，用list[]，-->用 PriorityQueue 优化
|0|1  |2| 3|4
| |3,4|2|  |1

第三步：从桶中倒数取前k个

三、解题方法

3.1 Java实现

public class Solution {
    public int[] topKFrequent(int[] nums, int k) {
        // 统计频数并记录最大频数值
        Map<Integer, Integer> countMap = new HashMap<>();
        int maxCount = 0;
        for (int tmp : nums) {
            // int tmpCount = countMap.containsKey(tmp) ? countMap.get(tmp) + 1 : 1;
            int tmpCount = countMap.getOrDefault(tmp, 0) + 1;
            maxCount = Math.max(maxCount, tmpCount);
            countMap.put(tmp, tmpCount);
        }

        // 构造桶
        List<Integer>[] listArr = new List[maxCount + 1];
        for (Integer tmp : countMap.keySet()) {
            int count = countMap.get(tmp);
            if (listArr[count] == null) {
                listArr[count] = new ArrayList<>();
            }
            listArr[count].add(tmp);
        }

        // 从桶中倒数取前k个
        List<Integer> resList = new ArrayList<>();
        for (int i = listArr.length - 1; i >= 0 && resList.size() < k; i--) {
            if (listArr[i] == null) {
                continue;
            }
            resList.addAll(listArr[i]);
        }
        return resList.stream().mapToInt(x -> x).toArray();
    }
}

3.2 java实现（优化）

class Solution {
    public int[] topKFrequent(int[] nums, int k) {
        // 堆排序 + 最大堆
        // 1、先统计数组中元素出现的个数，使用 HashMap 存储，一次遍历
        // 2、对元素个数进行堆排序，构建最大堆
        // 3、取出堆中前 k 个元素
        Map<Integer, Integer> map = new HashMap<>();
        for (int num : nums) {
            map.put(num, map.getOrDefault(num, 0) + 1);
        }
        PriorityQueue<int[]> priority = new PriorityQueue<>(new Comparator<int[]>(){
            public int compare(int[] num1, int[] num2) {
                return num2[1] - num1[1];
            }
        });
        for (int key : map.keySet()) {
            priority.offer(new int[]{key, map.get(key)});
        }
        int[] res = new int[k];
        for (int i = 0; i < k; i++) {
            res[i] = priority.poll()[0];
        }
        return res;
    }
}

四、总结小记

2022/5/22 今天好二呀，明显感受到夏天来啦。本题重点理解桶排序的思路，还有就是学习PriorityQueue类型，以前都没用过。

有关leetcode 347. Top K Frequent Elements 前 K 个高频元素的更多相关文章

ruby - 在哈希的键数组中追加元素 - 2
查看我的Ruby代码:h=Hash.new([])h[0]=:word1h[1]=h[1]输出是:Hash={0=>:word1,1=>[:word2,:word3],2=>[:word2,:word3]}我希望有Hash={0=>:word1,1=>[:word2],2=>[:word3]}为什么要附加第二个哈希元素(数组)？如何将新数组元素附加到第三个哈希元素？最佳答案如果您提供单个值作为Hash.new的参数(例如Hash.new([])，完全相同的对象将用作每个缺失键的默认值。这就是您所拥有的，那是你不想要的。您可以改用
「Python｜Selenium｜场景案例」如何定位iframe中的元素？ - 2
本文主要介绍在使用Selenium进行自动化测试或者任务时，对于使用了iframe的页面，如何定位iframe中的元素文章目录场景描述解决方案具体代码场景描述当我们在使用Selenium进行自动化测试的时候，可能会遇到一些界面或者窗体是使用HTML的iframe标签进行承载的。对于iframe中的标签，如果直接查找是无法找到的，会抛出没有找到元素的异常。比如近在咫尺的例子就是，CSDN的登录窗体就是使用的iframe，大家可以尝试通过F12开发者模式查看到的tag_name,class_name,id或者xpath来定位中的页面元素，会抛出NoSuchElementException异常。解决
Python 刷Leetcode题库，顺带学英语单词（31） - 2
ValidPalindromeGivenastring,determineifitisapalindrome,consideringonlyalphanumericcharactersandignoringcases. [#125]Example:"Aman,aplan,acanal:Panama"isapalindrome."raceacar"isnotapalindrome.Haveyouconsiderthatthestringmightbeempty?Thisisagoodquestiontoaskduringaninterview.Forthepurposeofthisproblem
ruby - Hanami link_to 助手只呈现最后一个元素 - 2
我是HanamiWorld的新人。我已经写了这段代码:moduleWeb::Views::HomeclassIndexincludeWeb::ViewincludeHanami::Helpers::HtmlHelperdeftitlehtml.headerdoh1'Testsearchengine',id:'title'hrdiv(id:'test')dolink_to('Home',"/",class:'mnu_orizontal')link_to('About',"/",class:'mnu_orizontal')endendendendend我在模板上调用了title方法。htm
ruby - 将n维数组的每个元素乘以Ruby中的数字 - 2
在Ruby中，是否有一种简单的方法可以将n维数组中的每个元素乘以一个数字？这样:[1,2,3,4,5].multiplied_by2==[2,4,6,8,10]和[[1,2,3],[1,2,3]].multiplied_by2==[[2,4,6],[2,4,6]]？(很明显，我编写了multiplied_by函数以区别于*，它似乎连接了数组的多个副本，不幸的是这不是我需要的)。谢谢! 最佳答案它的长格式等价物是:[1,2,3,4,5].collect{|n|n*2}其实并没有那么复杂。你总是可以使你的multiply_by方法:c
arrays - 计算数组中的匹配元素 - 2
给定两个大小相等的数组，如何找到不考虑位置的匹配元素的数量？例如:[0,0,5]和[0,5,5]将返回2的匹配项，因为有一个0和一个5共同；[1,0,0,3]和[0,0,1,4]将返回3的匹配项，因为0有两场，1有一场；[1,2,2,3]和[1,2,3,4]将返回3的匹配项。我尝试了很多想法，但它们都变得相当粗糙和令人费解。我猜想有一些不错的Ruby习惯用法，或者可能是一个正则表达式，可以很好地回答这个解决方案。最佳答案您可以使用count完成它:a.count{|e|index=b.index(e)andb.delete_at
ruby - 使用 Nokogiri 和 Ruby 命名元素 "text" - 2
我在尝试使用Nokogiri构建XML文档时遇到了一个小问题。我想将我的元素之一称为“文本”(请参阅下面粘贴代码的最底部)。通常，要创建一个新元素，我会执行类似以下的操作xml.text--但它似乎是.text是Nokogiri已经用来做其他事情的方法。因此，当我写这行时xml.textNokogiri没有创建名为的新元素但只是写了意味着成为元素内容的文本。我怎样才能让Nokogiri实际制作一个名为的元素？？builder=Nokogiri::XML::Builder.newdo|xml|xml.TEI("xmlns"=>"http://www.tei-c.org/ns/1.0"
ruby - 在 factory_girl 中有没有办法获取 attributes_for 并为同一个实例元素创建？ - 2
如果我想使用“create”构建策略创建和实例，然后想使用“attributes_for”构建策略进行验证，是否可以这样做？如果我在工厂中使用序列？在Machinistgem中有可能吗？最佳答案不太确定我是否完全理解。而且我不是机械师的用户。但听起来您只是想做这样的事情。@attributes=FactoryGirl.attributes_for(:my_object)my_object=MyObject.create(@attributes)my_object.some_property.should==@attributes
ruby - 数组数组中的唯一元素 - 2
我想通过内部数组中的第一个元素从数组数组中找到唯一元素。例如a=[[1,2],[2,3],[1,5]我想要类似的东西[[1,2],[2,3]] 最佳答案 uniq方法需要一个block:uniq_a=a.uniq(&:first)或者如果您想就地进行:a.uniq!(&:first)例如:>>a=[[1,2],[2,3],[1,5]]=>[[1,2],[2,3],[1,5]]>>a.uniq(&:first)=>[[1,2],[2,3]]>>a=>[[1,2],[2,3],[1,5]]或者>>a=[[1,2],[2,3],[1,5]
arrays - 在一行中选择数组的第一个和最后一个元素 - 2
我的任务是从数组中选择最高和最低的数字。我想我很清楚我想做什么，但只是努力以正确的格式访问信息以满足通过标准。defhigh_and_low(numbers)array=numbers.split("").map!{|x|x.to_i}array.sort!{|a,b|ba}putsarray[0,-1]end数字可能看起来像"80917234100"，要通过，我需要输出"9234"。我正在尝试putsarray.first.last，但一直无法弄明白。最佳答案有Array#minmax完全满足您需要的方法:array=[80,