題目
題目描述
- 設計一個類似 stack 的資料結構，實行
push()跟pop()的功能，其中pop()會丟出 stack 中出現最多次的元素。 - FreqStack class 必須實現：
FreqStack()建構子必須初始化一個空的 FreqStack。void push(int val)將val推至 stack 的頂端。int pop()將 stack 中最頻繁出現的元素移除，並返回。- 如果 stack 中最頻繁出現的元素出現平手的狀況，則返回平手的元素中最接近 stack 頂端的元素。
題目範例
輸入
[“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 freqStack = new FreqStack();
freqStack.push(5); // The stack is [5]
freqStack.push(7); // The stack is [5,7]
freqStack.push(5); // The stack is [5,7,5]
freqStack.push(7); // The stack is [5,7,5,7]
freqStack.push(4); // The stack is [5,7,5,7,4]
freqStack.push(5); // The stack is [5,7,5,7,4,5]
freqStack.pop(); // return 5, as 5 is the most frequent. The stack becomes [5,7,5,7,4].
freqStack.pop(); // return 7, as 5 and 7 is the most frequent, but 7 is closest to the top. The stack becomes [5,7,5,4].
freqStack.pop(); // return 5, as 5 is the most frequent. The stack becomes [5,7,4].
freqStack.pop(); // return 4, as 4, 5 and 7 is the most frequent, but 4 is closest to the top. The stack becomes [5,7].解題
想法
- 在解題時，我打算在 push 時動手腳，將 push 的元素直接 push 到對的位置後，執行 pop 的動作時，就只要將最頂端的元素取出即可。
FreqStack 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]
// 此時 4 因為並非最頻繁的元素，所以要將 4 往下推，即變成 [5,7,4,5,7]
freqStack.push(5); // [5,7,4,5,7,5]
freqStack.pop(); // return 5, [5,7,4,5,7]
freqStack.pop(); // return 7, [5,7,4,5]
freqStack.pop(); // return 5, [5,7,4]
freqStack.pop(); // return 4, [5,7]- 為了實現以上的想法，我試想將出現次數相同的元素放在同一個 stack，取出時則從頻率最高的 stack 開始取，即為：
freqStack[0] = [5,7,4] // 檢查元素是否出現在 freqStack[0] 否則則往freqStack[1] 移動
freqStack[1] = [5,7]
freqStack[2] = [5] // pop 的時候，從freqStack[2] 開始取，空了則將 freqStack[2] 移除實作1: List of Stacks
public class freqStack{
// Field
List<Stack<Integer>> stacks;
// Constructor
public freqStack(){
stacks = new ArrayList<>();
}
// Methods
public void push(int val){
push(val, 0);
}
private void push(int val, int freq){
// 當 stacks[freq] 是空的時候，則新建一個 stack。
Stack<Integer> stack;
if (freq >= stacks.size()){
stack = new Stack<>();
stacks.add(stack);
} else {
stack = stacks.get(freq);
}
// 當該 stacks[freq] 已經有該元素，則往下一個 stacks 找
if (stack.contains(val)){
push(val, freq + 1);
} else {
stack.push(val);
}
}
public int pop(){
// 直接找到最高的 stack，然後把頂端的元素 pop 出。
Stack<Integer> stack = stacks.get(stacks.size() - 1);
int top = stack.pop();
if (stack.isEmpty()){
stacks.remove(stacks.size() - 1);
}
return top;
}
}- 然而，此時 push 的 complexity 與欲 push 的元素的出現次數 n 有關，元素出現 n 次，則需要往下找 n 個 stack，也就是 \(O(n)\)。
實作2: Use HashMap to record freqency
- 為了優化，我們可以加入一個 HashMap 來記錄出現的次數，再下次要 push 此元素時，只需要到 HashMap 中查詢出現的次數即可。
public class freqStack{
// Field
List<Stack<Integer>> stacks;
Map<Integer, Integer> map; // 用來記錄出現次數
// Constructor
public freqStack(){
stacks = new ArrayList<>();
map = new HashMap();
}
// Methods
public void push(int val){
Stack<Integer> stack;
// 還沒有此出現次數的元素出現，則新增此 stack
if (stacks.size() < map.getOrDefault(val, 0) + 1){
stack = new Stack<>();
} else {
// 取得此元素出現的次數，若沒出現過則取得 stacks[0]
stack = stacks.get(map.getOrDefault(val, 0));
}
stack.push(val);
map.put(val, map.getOrDefault(val, 0) + 1); // 更新出現次數
}
public int pop(){
// 直接找到最高的 stack，然後把頂端的元素 pop 出。
Stack<Integer> stack = stacks.get(stacks.size() - 1);
int top = stack.pop();
map.put(val, map.get(val) - 1); // 更新出現次數
if (stack.isEmpty()){
stacks.remove(stacks.size() - 1);
}
return top;
}
}程式碼
Reference: Leetcode: 895. Maximum Frequency Stack