[Leetcode859]最大频率栈

echoqiqi 2023-03-28 原文

1.题目

设计一个类似堆栈的数据结构，将元素推入堆栈，并从堆栈中弹出出现频率最高的元素。

实现 FreqStack 类:

FreqStack() 构造一个空的堆栈。
void push(int val) 将一个整数 val 压入栈顶。
int pop() 删除并返回堆栈中出现频率最高的元素。
- 如果出现频率最高的元素不只一个，则移除并返回最接近栈顶的元素。

示例 1：

输入：
["FreqStack","push","push","push","push","push","push","pop","pop","pop","pop"],
[[],[5],[7],[5],[7],[4],[5],[],[],[],[]]
输出：[null,null,null,null,null,null,null,5,7,5,4]
解释：
FreqStack = new FreqStack();
freqStack.push (5);//堆栈为 [5]
freqStack.push (7);//堆栈是 [5,7]
freqStack.push (5);//堆栈是 [5,7,5]
freqStack.push (7);//堆栈是 [5,7,5,7]
freqStack.push (4);//堆栈是 [5,7,5,7,4]
freqStack.push (5);//堆栈是 [5,7,5,7,4,5]
freqStack.pop ();//返回 5 ，因为 5 出现频率最高。堆栈变成 [5,7,5,7,4]。
freqStack.pop ();//返回 7 ，因为 5 和 7 出现频率最高，但7最接近顶部。堆栈变成 [5,7,5,4]。
freqStack.pop ();//返回 5 ，因为 5 出现频率最高。堆栈变成 [5,7,4]。
freqStack.pop ();//返回 4 ，因为 4, 5 和 7 出现频率最高，但 4 是最接近顶部的。堆栈变成 [5,7]。

提示：

0 <= val <= 109
push 和 pop 的操作数不大于 2 * 104。
输入保证在调用 pop 之前堆栈中至少有一个元素。

2.思路

我的是想法是用一个Map数据结构记录每个元素的频率，然后pop操作，找到最大的频率，然后从后往前遍历stack数组，返回频率为最大频率的数，并进行删除。在这个过程中，涉及到map的插入和删除，vector元素的删除操作，我觉得是有意义的部分。看了题解，是以空间换时间，每个频率一个stack感觉思路也很巧妙。

3.代码

我的代码：

class FreqStack {
public:
    vector<int>stack;
    map<int,int>frequency;
    FreqStack() {
    }
    
    void push(int val) {
        if(frequency.count(val)==0)//直接插入
        {
            frequency[val]=1;
        }
        else frequency[val]++;
        stack.emplace_back(val);
    }
    int pop() {
        int mx=0;
        int result=0;
        map<int,int>::iterator iter;
        for(iter=frequency.begin();iter!=frequency.end();iter++)
        {
            int fre=iter->second;
            int key=iter->first;
            if(fre>mx)
            {
                mx=fre;
            }
        }
        int len=stack.size();
        for(int i=len-1;i>=0;i--)
        {
            int num=stack[i];
            if(frequency[num] == mx)
            {
                result=num;
                frequency[num]--;
                if(frequency[num]==0) frequency.erase(num);//删除元素,key为num
                stack.erase((stack.begin()+i));//删除元素
                break;
            }
        }
        return result;
    }
};

/**
 * Your FreqStack object will be instantiated and called as such:
 * FreqStack* obj = new FreqStack();
 * obj->push(val);
 * int param_2 = obj->pop();
 */

题解的代码：

class FreqStack {
public:
    FreqStack() {
        maxFreq = 0;
    }

    void push(int val) {
        freq[val]++;
        group[freq[val]].push(val);
        maxFreq = max(maxFreq, freq[val]);
    }

    int pop() {
        int val = group[maxFreq].top();
        freq[val]--;
        group[maxFreq].pop();
        if (group[maxFreq].empty()) {
            maxFreq--;
        }
        return val;
    }

private:
    unordered_map<int, int> freq;
    unordered_map<int, stack<int>> group;
    int maxFreq;
};

有关[Leetcode859]最大频率栈的更多相关文章

Python 刷Leetcode题库，顺带学英语单词（31） - 2
ValidPalindromeGivenastring,determineifitisapalindrome,consideringonlyalphanumericcharactersandignoringcases. [#125]Example:"Aman,aplan,acanal:Panama"isapalindrome."raceacar"isnotapalindrome.Haveyouconsiderthatthestringmightbeempty?Thisisagoodquestiontoaskduringaninterview.Forthepurposeofthisproblem
ruby-on-rails - 需要帮助最大化多个相似对象中的 3 个因素并适当排序 - 2
我需要用任何语言编写一个算法，根据3个因素对数组进行排序。我以度假村为例(如Hipmunk)。假设我想去度假。我想要最便宜的地方、最好的评论和最多的景点。但是，显然我找不到在所有3个中都排名第一的方法。Example(assumingthereare20importantattractions):ResortA:$150/night...98/100infavorablereviews...18of20attractionsResortB:$99/night...85/100infavorablereviews...12of20attractionsResortC:$120/night
ruby - 获取数组中值的最大连续出现次数 - 2
下面有没有更优雅的方法来实现这个:输入:array=[1,1,1,0,0,1,1,1,1,0]输出:4我的算法:streak=0max_streak=0arr.eachdo|n|ifn==1streak+=1elsemax_streak=streakifstreak>max_streakstreak=0endendputsmax_streak 最佳答案类似于w0lf'sanswer,但通过从chunk返回nil来跳过元素:array.chunk{|x|x==1||nil}.map{|_,x|x.size}.max
IDEA使用LeetCode插件 - 2
前言我们习惯用idea编写、调试代码，在LeetCode上刷题时，如果能够在IDEA编写代码，并且做好代码管理，是一件事半功倍的事情。对于后续复习题目，做笔记也会非常便利。本文目的在于介绍LeetCodeEditor的使用，以及配置工具类，最终目录结构如下：note：放置笔记src：放置代码leetcode.editor.cn：插件LeetCodeEditor自动生成utils：自定义的工具包，可用于自动化输入测试用例，定义题目需要的类（结构体）out：运行测试时自动生成LeetCodeEditorGitHub：https://github.com/shuzijun/leetcode-edit
ruby - 按数组中出现的频率排序 - 2
有没有一种有效的方法来做到这一点。我有一个数组a=[1,2,2,3,1,2]我想按升序输出出现的频率。示例[[3,1],[1,2],[2,3]]这是我的ruby代码。b=a.group_by{|x|x}out={}b.eachdo|k,v|out[k]=v.sizeendout.sort_by{|k,v|v} 最佳答案 a=[1,2,2,3,1,2]a.each_with_object(Hash.new(0)){|m,h|h[m]+=1}.sort_by{|k,v|v}#=>[[3,1],[1,2],[2,3]]
ruby - capybara 增加最大允许页面加载时间 - 2
我有一个页面，有时加载时间超过一分钟。假设这是预期的行为并且不会改变。在这些情况下，我得到Net::ReadTimeout。请注意，这是在通过单击上一页上的按钮导航到页面之后，而不是ajax请求。因此Capybara.using_wait_time没有帮助。我尝试了一些激进的方法(其中一些我知道行不通)，例如:设置page.driver.browser.manage.timeouts的implicit_wait、script_timeout和page_load。遍历整个对象空间并设置所有Selenium::WebDriver::Remote::Http::Default的timeout
Ruby - 找到哈希最大值的键 - 2
我有一个散列，我想返回散列最大值的键(或键/值对)。所以，如果只有一个真正的最大值，它将返回那个键；但是，如果有多个具有相同值的键/值对，它将返回所有这些键。我如何在Ruby中完成此操作？my_hash.max_by{|k,v|v}#onlyreturnsonekey/valuepair 最佳答案如果你想要所有对，我会做类似的事情max=my_hash.values.maxHash[my_hash.select{|k,v|v==max}] 关于Ruby-找到哈希最大值的键，我们在Sta
ruby-on-rails - 在 Ruby on Rails 中根据频率对数组进行排序 - 2
我有一个嵌套的数字数组，排列如下:ids=[[5,8,10],[8,7,25],[15,30,32],[10,8,7]]我只需要一个包含所有键的数组，无需重复，所以我使用了这个:ids=ids.flatten.uniq产生这个:ids=[5,8,10,7,25,15,30,32]由于我使用了.uniq，它消除了重复值。但是，我想根据它们在子数组中出现的频率来对值进行排序，而不是它们碰巧处于的顺序——所以像这样:ids=[8,10,7,5,25,15,30,32] 最佳答案应该这样做:ids.flatten.group_by{|i|
Ruby:获取具有最大值的哈希对 - 2
这是一个哈希值，用于跟踪我拥有的每种水果的数量fruits={"apples"=>10,"pears"=>15,"bananas"=>15,"grapes"=>12}我想知道哪种水果我吃得最多。如果有决胜局，则将它们全部归还。最佳答案 #easymax_quantity=fruits.values.maxmax_fruits=fruits.select{|k,v|v==max_quantity}.keys#fastmax_quantity=-1.0/0.0max_fruits=[]fruits.eachdo|k,v|ifv>max
ruby-on-rails - 如何在 ruby 中找到跨记录的最大属性？ - 2
我有几个具有多个属性(A、B、C、D)的记录。我希望能够找到哪条记录对于给定属性(例如D)具有更高的值。我该怎么做？最佳答案你可能会给出max_by一看。objects=[somearrayofobjects]object_with_highest_value=objects.max_by{|obj|obj.desired_value} 关于ruby-on-rails-如何在ruby中找到跨记录的最大属性？，我们在StackOverflow上找到一个类似的问题：

[Leetcode859]最大频率栈

1.题目

2.思路

3.代码

有关[Leetcode859]最大频率栈的更多相关文章

随机推荐