Сложность: hard
Разработайте структуру данных, похожую на стек, чтобы заталкивать элементы в стек и вытаскивать из него самый частый элемент. Реализуйте класс FreqStack: FreqStack() строит пустой стек частот. void push(int val) заталкивает целое число val на вершину стека. int pop() удаляет и возвращает самый частый элемент в стеке. Если есть равенство в выборе самого частого элемента, то удаляется и возвращается элемент, который ближе всего к вершине стека.
Пример:
Input
["FreqStack", "push", "push", "push", "push", "push", "push", "pop", "pop", "pop", "pop"]
[[], [5], [7], [5], [7], [4], [5], [], [], [], []]
Output
[null, null, null, null, null, null, null, 5, 7, 5, 4]
👨💻 Алгоритм:
1⃣Создать два словаря: freq для хранения частоты каждого элемента и group для хранения стека элементов для каждой частоты.
2⃣При добавлении элемента увеличивать его частоту в freq и добавлять его в стек соответствующей частоты в group.
3⃣При извлечении элемента найти максимальную частоту, удалить элемент из стека соответствующей частоты и уменьшить его частоту в freq. Если стек для данной частоты становится пустым, удалить его.
😎 Решение:
class FreqStack {
private var freq: [Int: Int]
private var group: [Int: [Int]]
private var maxfreq: Int
init() {
freq = [:]
group = [:]
maxfreq = 0
}
func push(_ val: Int) {
let f = (freq[val] ?? 0) + 1
freq[val] = f
if f > maxfreq {
maxfreq = f
group[f] = []
}
group[f]?.append(val)
}
func pop() -> Int {
guard let val = group[maxfreq]?.popLast() else { return -1 }
freq[val, default: 0] -= 1
if group[maxfreq]?.isEmpty ?? false {
maxfreq -= 1
}
return val
}
}Ставь 👍 и забирай 📚 Базу знаний