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;
};

轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/538832.html

標籤：其他

上一篇：鏈表基礎知識

下一篇：「哈希表」最大頻率堆疊(力扣第895題)

[Leetcode859]最大頻率堆疊

1.題目

2.思路

3.代碼