• 设为首页
  • 点击收藏
  • 手机版
    手机扫一扫访问
    迪恩网络手机版
  • 关注官方公众号
    微信扫一扫关注
    公众号

[Swift]LeetCode895.最大频率栈|MaximumFrequencyStack

原作者: [db:作者] 来自: [db:来源] 收藏 邀请

★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★
➤微信公众号:山青咏芝(shanqingyongzhi)
➤博客园地址:山青咏芝(https://www.cnblogs.com/strengthen/
➤GitHub地址:https://github.com/strengthen/LeetCode
➤原文地址: https://www.cnblogs.com/strengthen/p/10605780.html 
➤如果链接不是山青咏芝的博客园地址,则可能是爬取作者的文章。
➤原文已修改更新!强烈建议点击原文地址阅读!支持作者!支持原创!
★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★

热烈欢迎,请直接点击!!!

进入博主App Store主页,下载使用各个作品!!!

注:博主将坚持每月上线一个新app!!!

Implement FreqStack, a class which simulates the operation of a stack-like data structure.

FreqStack has two functions:

  • push(int x), which pushes an integer x onto the stack.
  • pop(), which removes and returns the most frequent element in the stack.
    • If there is a tie for most frequent element, the element closest to the top of the stack is removed and returned. 

Example 1:

Input: 
[[],[5],[7],[5],[7],[4],[5],[],[],[],[]]
Output: [null,null,null,null,null,null,null,5,7,5,4]
Explanation:
After making six .push operations, the stack is [5,7,5,7,4,5] from bottom to top.  Then:

pop() -> returns 5, as 5 is the most frequent.
The stack becomes [5,7,5,7,4].

pop() -> returns 7, as 5 and 7 is the most frequent, but 7 is closest to the top.
The stack becomes [5,7,5,4].

pop() -> returns 5.
The stack becomes [5,7,4].

pop() -> returns 4.
The stack becomes [5,7]. 

Note:

  • Calls to FreqStack.push(int x) will be such that 0 <= x <= 10^9.
  • It is guaranteed that FreqStack.pop() won't be called if the stack has zero elements.
  • The total number of FreqStack.push calls will not exceed 10000 in a single test case.
  • The total number of FreqStack.pop calls will not exceed 10000 in a single test case.
  • The total number of FreqStack.push and FreqStack.pop calls will not exceed 150000 across all test cases.

实现 FreqStack,模拟类似栈的数据结构的操作的一个类。

FreqStack 有两个函数:

  • push(int x),将整数 x 推入栈中。
  • pop(),它移除并返回栈中出现最频繁的元素。
    • 如果最频繁的元素不只一个,则移除并返回最接近栈顶的元素。 

示例:

输入:
["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]
解释:
执行六次 .push 操作后,栈自底向上为 [5,7,5,7,4,5]。然后:

pop() -> 返回 5,因为 5 是出现频率最高的。
栈变成 [5,7,5,7,4]。

pop() -> 返回 7,因为 5 和 7 都是频率最高的,但 7 最接近栈顶。
栈变成 [5,7,5,4]。

pop() -> 返回 5 。
栈变成 [5,7,4]。

pop() -> 返回 4 。
栈变成 [5,7]。 

提示:

  • 对 FreqStack.push(int x) 的调用中 0 <= x <= 10^9
  • 如果栈的元素数目为零,则保证不会调用  FreqStack.pop()
  • 单个测试样例中,对 FreqStack.push 的总调用次数不会超过 10000
  • 单个测试样例中,对 FreqStack.pop 的总调用次数不会超过 10000
  • 所有测试样例中,对 FreqStack.push 和 FreqStack.pop 的总调用次数不会超过 150000。 

Runtime: 920 ms
Memory Usage: 22.3 MB
 1 class FreqStack {
 2     var freq:[Int:Int]
 3     var m:[Int:[Int]]
 4     var maxfreq:Int
 5     init() {
 6         freq = [Int:Int]()
 7         m = [Int:[Int]]()
 8         maxfreq = 0        
 9     }
10     
11     func push(_ x: Int) {
12         var f:Int = freq[x,default:0] + 1
13         freq[x] = f
14         maxfreq = max(maxfreq, f)
15         m[f,default:[Int]()].append(x)      
16     }
17     
18     func pop() -> Int {
19         var x:Int = m[maxfreq,default:[Int]()].popLast() ?? 0
20         freq[x] = maxfreq - 1
21         if m[maxfreq,default:[Int]()].count == 0 {maxfreq -= 1}
22         return x     
23     }
24 }
25 
26 /**
27  * Your FreqStack object will be instantiated and called as such:
28  * let obj = FreqStack()
29  * obj.push(x)
30  * let ret_2: Int = obj.pop()
31  */
32  

1016ms

 1 class FreqStack {
 2     
 3     var appearancesByValues = [Int: Int]()
 4     var valuesByAppearances = [Int: [Int]]()
 5 
 6     var maxAppearances = 1
 7     let emptySet = Set<Int>()
 8 
 9     init() {
10 
11     }
12 
13     func push(_ x: Int) {
14 
15         let appearances = self.appearancesByValues[x, default: 0] + 1
16         self.appearancesByValues[x] = appearances
17 
18         if appearances > self.maxAppearances {
19             self.maxAppearances = appearances
20         }
21         self.valuesByAppearances[appearances, default: []].append(x)
22 
23     }
24 
25     func pop() -> Int {
26 
27         let value = (self.valuesByAppearances[self.maxAppearances]?.popLast())!
28 
29         self.appearancesByValues[value]! -= 1
30 
31         if self.valuesByAppearances[self.maxAppearances]?.count == 0 {
32             self.maxAppearances -= 1
33         }
34 
35         return value
36     }
37 }

1024ms

 1 class FreqStack {
 2     
 3     var freq: [Int: Int] // num: freq
 4     var group: [Int: [Int]] // freq: stack of elements w/ same freq
 5     var maxFreq: Int
 6 
 7     init() {
 8         self.freq = [Int: Int]()
 9         self.group = [Int: [Int]]()
10         self.maxFreq = 0
11     }
12     
13     func push(_ x: Int) {
14         let f = (freq[x] ?? 0) + 1
15         freq[x] = f
16         if var stack = group[f] {
17             stack.append(x)
18             group[f] = stack
19         } else {
20             group[f] = [x]
21         }
22         if f > maxFreq {
23             maxFreq = f
24         }
25     }
26     
27     func pop() -> Int {
28         var stack = group[maxFreq]!
29         let result = stack.removeLast()
30         freq[result] = maxFreq - 1
31         group[maxFreq] = stack
32         if stack.count == 0 {
33             maxFreq -= 1
34         }
35         return result
36     }
37 }

1068ms

 1 class FreqStack {
 2 
 3     init() {
 4         
 5     }
 6     
 7     func push(_ x: Int) {
 8         let f = elem2Freq[x, default: 0] + 1
 9         elem2Freq[x] = f
10         let sz = subStacks.count
11         if f >= sz {
12             subStacks.append([x])
13         } else {
14             subStacks[f].append(x)
15         }
16     }
17     
18     func pop() -> Int {
19         let sz = subStacks.count
20         let x = subStacks[sz - 1].popLast()!
21         if subStacks[sz - 1].isEmpty {
22             subStacks.removeLast()
23         }
24         elem2Freq[x, default: 0] -= 1
25         return x
26     }
27     
28     var elem2Freq = [Int: Int]()
29     var subStacks = [[Int]()]
30 }

1432ms

  1 public struct PriorityQueue<T: Comparable> {    
  2     fileprivate var heap = [T]()
  3     private let ordered: (T, T) -> Bool
  4     
  5     public init(ascending: Bool = false, startingValues: [T] = []) {
  6         self.init(order: ascending ? { $0 > $1 } : { $0 < $1 }, startingValues: startingValues)
  7     }
  8     
  9     // Creates a new PriorityQueue with the given ordering.
 10     // - parameter order: A function that specifies whether its first argument should
 11     //   come after the second argument in the PriorityQueue.
 12     // - parameter startingValues: An array of elements to initialize the PriorityQueue with.
 13     public init(order: @escaping (T, T) -> Bool, startingValues: [T] = []) {
 14         ordered = order
 15         
 16         //Based on "Heap construction" from Sedgewick p 323
 17         heap = startingValues
 18         var i = heap.count/2 - 1
 19         while i >= 0 {
 20             sink(i)
 21             i -= 1
 22         }
 23     }
 24     
 25     // How many elements the Priority Queue stores
 26     public var count: Int { return heap.count }
 27     
 28     // true if and only if the Priority Queue is empty
 29     public var isEmpty: Bool { return heap.isEmpty }
 30     
 31     // Add a new element onto the Priority Queue. O(lg n)
 32     // - parameter element: The element to be inserted into the Priority Queue.
 33     public mutating func push(_ element: T) {
 34         heap.append(element)
 35         swim(heap.count - 1)
 36     }
 37     
 38     // Remove and return the element with the highest priority (or lowest if ascending). O(lg n)
 39     // - returns: The element with the highest priority in the Priority Queue, or nil if the PriorityQueue is empty.
 40     public mutating func pop() -> T? {
 41         
 42         if heap.isEmpty { return nil }
 43         // added for Swift 2 compatibility
 44         if heap.count == 1 { return heap.removeFirst() } 
 45         // so as not to call swap() with two instances of the same location
 46         heap.swapAt(0, heap.count - 1)
 47         let temp = heap.removeLast()
 48         sink(0)
 49         
 50         return temp
 51     }
 52     
 53     private mutating func sink(_ index: Int) {
 54         var index = index
 55         while 2 * index + 1 < heap.count {            
 56             var j = 2 * index + 1            
 57             if j < (heap.count - 1) && ordered(heap[j], heap[j + 1]) { j += 1 }
 58             if !ordered(heap[index], heap[j]) { break }            
 59             heap.swapAt(index, j)
 60             index = j
 61         }
 62     }
 63     
 64     // Based on example from Sedgewick p 316
 65     private mutating func swim(_ index: Int) {
 66         var index = index
 67         while index > 0 && ordered(heap[(index - 1) / 2], heap[index]) {
 68             heap.swapAt((index - 1) / 2, index)
 69             index = (index - 1) / 2
 70         }
 71     }
 72 }
 73 
 74 struct Entry: Comparable {
 75     let x: Int
 76     let priority: Int
 77     
 78     static func == (lhs: Entry, rhs: Entry) -> Bool {
 79         return lhs.priority == rhs.priority
 80     }
 81     
 82     static func < (lhs: Entry, rhs: Entry) -> Bool {
 83         return lhs.priority < rhs.priority
 84     }
 85     
 86     static func <= (lhs: Entry, rhs: Entry) -> Bool {
 87         return lhs.priority <= rhs.priority
 88     }
 89 
 90     static func > (lhs: Entry, rhs: Entry) -> Bool {
 91         return lhs.priority > rhs.priority
 92     }
 93     
 94     static func >= (lhs: Entry, rhs: Entry) -> Bool {
 95         return lhs.priority >= rhs.priority
 96     }
 97 }
 98 
 99 class FreqStack {
100     
101     var pq: PriorityQueue<Entry>
102     var freq: [Int: Int] = [:]
103     
104     init() {
105         pq = PriorityQueue<Entry>(ascending: false, startingValues: [])
106     }
107     
108     let maxN = 10000
109     var pushCount = 0
110     func push(_ x: Int) {
111         let count = freq[x, default: 0] + 1
112         freq[x] = count
113         pushCount += 1
114         pq.push(Entry(x: x, priority:  count * maxN + pushCount))
115     }
116     
117     func pop() -> Int {
118         let entry = pq.pop()!
119         freq[entry.x] = freq[entry.x]! - 1
120         return entry.x
121     }
122 }
123 
124 /**
125  * Your FreqStack object will be instantiated and called as such:
126  * let obj = FreqStack()
127  * obj.push(x)
128  * let ret_2: Int = obj.pop()
129  */

 


鲜花

握手

雷人

路过

鸡蛋
该文章已有0人参与评论

请发表评论

全部评论

专题导读
热门推荐
热门话题
阅读排行榜

扫描微信二维码

查看手机版网站

随时了解更新最新资讯

139-2527-9053

在线客服(服务时间 9:00~18:00)

在线QQ客服
地址:深圳市南山区西丽大学城创智工业园
电邮:jeky_zhao#qq.com
移动电话:139-2527-9053

Powered by 互联科技 X3.4© 2001-2213 极客世界.|Sitemap