[Swift]LeetCode347.前K个高频元素|TopKFrequentElements

OStack程序员社区-中国程序员成长平台 › 门户 › 编程› 移动开发›Swift 教程

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

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

热烈欢迎，请直接点击！！！

进入博主App Store主页，下载使用各个作品！！！

注：博主将坚持每月上线一个新app！！！

Given a non-empty array of integers, return the k most frequent elements.

Example 1:

Input: nums = 2
Output: [1,2]

Example 2:

Input: nums = 1
Output: [1]

Note:

You may assume k is always valid, 1 ≤ k ≤ number of unique elements.
Your algorithm's time complexity must be better than O(n log n), where n is the array's size.

给定一个非空的整数数组，返回其中出现频率前 k 高的元素。

示例 1:

输入: nums = [1,1,1,2,2,3], k = 2
输出: [1,2]

示例 2:

输入: nums = [1], k = 1
输出: [1]

说明：

你可以假设给定的 k 总是合理的，且 1 ≤ k ≤ 数组中不相同的元素的个数。
你的算法的时间复杂度必须优于 O(n log n) , n 是数组的大小。

推荐1（助力理解优先队列）：

  1 public struct Heap<T> {
  2     public var nodes = [T]()
  3     private var orderCriteria: (T, T) -> Bool
  4     
  5     public init(sort: @escaping (T, T) -> Bool) {
  6         orderCriteria = sort
  7     }
  8     
  9     public init(array: [T], sort: @escaping (T, T) -> Bool) {
 10         self.orderCriteria = sort
 11         configureHeap(from: array)
 12     }
 13     
 14     public var isEmpty: Bool {
 15         return nodes.isEmpty
 16     }
 17     
 18     public var count: Int {
 19         return nodes.count
 20     }
 21     
 22     public mutating func configureHeap(from array: [T]) {
 23         nodes = array
 24         for i in stride(from: nodes.count / 2 - 1, through: 0, by: -1) {
 25             shiftDown(i)
 26         }
 27     }
 28     
 29     public mutating func reset() {
 30         for i in stride(from: nodes.count / 2 - 1, through: 0, by: -1) {
 31             shiftDown(i)
 32         }
 33     }
 34     
 35     @inline(__always) internal func parentIndex(ofIndex index: Int) -> Int {
 36         return (index - 1) / 2
 37     }
 38     
 39     @inline(__always) internal func leftChildIndex(ofIndex index: Int) -> Int {
 40         return index * 2 + 1
 41     }
 42     
 43     @inline(__always) internal func rightChildIndex(ofIndex index: Int) -> Int {
 44         return index * 2 + 2
 45     }
 46     
 47     public func peek() -> T? {
 48         return nodes.first
 49     }
 50     
 51     internal mutating func shiftUp(_ index: Int) {
 52         var childIndex = index
 53         let child = nodes[childIndex]
 54         var parentIndex = self.parentIndex(ofIndex: index)
 55         while childIndex > 0 && orderCriteria(child, nodes[parentIndex]) {
 56             nodes[childIndex] = nodes[parentIndex]
 57             childIndex = parentIndex
 58             parentIndex = self.parentIndex(ofIndex: childIndex)
 59         }
 60         nodes[childIndex] = child
 61     }
 62     
 63     internal mutating func shiftDown(from index: Int, until endIndex: Int) {
 64         let leftChildIndex = self.leftChildIndex(ofIndex: index)
 65         let rightChildIndex = self.rightChildIndex(ofIndex: index)
 66         
 67         var first = index
 68         if leftChildIndex < endIndex && orderCriteria(nodes[leftChildIndex], nodes[first]) {
 69             first = leftChildIndex
 70         }
 71         if rightChildIndex < endIndex && orderCriteria(nodes[rightChildIndex], nodes[first]) {
 72             first = rightChildIndex
 73         }
 74         if first == index {
 75             return
 76         }
 77         nodes.swapAt(index, first)
 78         shiftDown(from: first, until: endIndex)
 79     }
 80     
 81     internal mutating func shiftDown(_ index: Int) {
 82         shiftDown(from: index, until: nodes.count)
 83     }
 84     
 85     public mutating func insert(_ value: T) {
 86         nodes.append(value)
 87         shiftUp(nodes.count - 1)
 88     }
 89     
 90     public mutating func insert<S: Sequence>(_ sequence:S) where S.Iterator.Element == T {
 91         for value in sequence {
 92             insert(value)
 93         }
 94     }
 95     
 96     public mutating func replace(index i: Int, value: T) {
 97         guard i < nodes.count else {
 98             return
 99         }
100         remove(at: i)
101         insert(value)
102     }
103     
104     @discardableResult
105     public mutating func remove() -> T? {
106         guard !nodes.isEmpty else {
107             return nil
108         }
109         if nodes.count == 1 {
110             return nodes.removeLast()
111         } else {
112             let value = nodes[0]
113             nodes[0] = nodes.removeLast()
114             shiftDown(0)
115             return value
116         }
117     }
118     
119     @discardableResult
120     public mutating func remove(at index: Int) -> T? {
121         guard index < nodes.count else { return nil}
122         let size = nodes.count - 1
123         if index != size {
124             nodes.swapAt(index, size)
125             shiftDown(from: index,  until: size)
126             shiftUp(index)
127         }
128         return nodes.removeLast()
129     }
130     
131     public mutating func sort() -> [T] {
132         for i in stride(from: self.nodes.count - 1, to: 0, by: -1) {
133             nodes.swapAt(0, i)
134             shiftDown(from: 0, until: i)
135         }
136         return nodes
137     }
138 
139 }
140 
141 
142 class Solution {
143     func topKFrequent(_ nums: [Int], _ k: Int) -> [Int] {
144         var heap = Heap<(Int, Int)>.init { (f, s) -> Bool in
145             return f.1 < s.1
146         }
147         var dict = [Int: Int]()
148         for i in nums {
149             dict[i] = (dict[i] ?? 0) + 1
150         }
151         
152         for i in dict {
153             heap.insert(i)
154             if heap.count > k {
155                 heap.remove()
156             }
157         }
158         var array = [Int]()
159         while heap.count > 0 {
160             array.append(heap.peek()!.0)
161             heap.remove()
162         }
163         return array.reversed()
164     }
165 }

推荐2（助力理解优先队列）：

  1 class Solution {
  2     func topKFrequent(_ nums: [Int], _ k: Int) -> [Int] {
  3         
  4         let numCount = self.countNums(nums)
  5         
  6         var heap = MinHeap<NumberCount>([])
  7         
  8         for n in numCount{
  9             heap.add(n)
 10             if heap.count > k{
 11                 heap.poll()
 12             }
 13         }
 14         
 15         var result = [Int]()
 16         
 17         while heap.peek() != nil{
 18             let currentN = heap.poll()
 19             result.append(currentN.n)
 20         }
 21         
 22         result.reverse()
 23         
 24         return result
 25     }
 26     
 27     func countNums(_ nums:[Int]) -> [NumberCount]{
 28         
 29         var dict = [Int:Int]()
 30         for n in nums{
 31             var count = dict[n] ?? 0
 32             count += 1
 33             dict[n] = count
 34         }
 35         
 36         var result = [NumberCount]()
 37         
 38         for(k,v) in dict{
 39             let newN = NumberCount(k, v)
 40             result.append(newN)
 41         }
 42         
 43         return result
 44     }
 45 }
 46 
 47 class MinHeap<T:Comparable>{
 48     
 49     var data:[T]
 50     
 51     init(_ data:[T]){
 52         self.data = data
 53     }
 54     
 55     func parent(_ index:Int) -> T{
 56         return self.data[self.parentIndex(index)]
 57     }
 58     
 59     func leftChild(_ index:Int) -> T{
 60         return self.data[self.leftChildIndex(index)]
 61     }
 62     
 63     func rightChild(_ index:Int) -> T{
 64         return self.data[self.rightChildIndex(index)]
 65     }
 66     
 67     func parentIndex(_ index:Int) -> Int{
 68         return (index - 1) / 2
 69     }
 70     
 71     func leftChildIndex(_ index:Int) -> Int{
 72         return index * 2 + 1
 73     }
 74     
 75     func rightChildIndex(_ index:Int) -> Int{
 76         return index * 2 + 2
 77     }
 78     
 79     func hasParent(_ index:Int) -> Bool{
 80         return self.parentIndex(index) >= 0
 81     }
 82     
 83     func hasLeftChild(_ index:Int) -> Bool{
 84         return self.leftChildIndex(index) < self.count
 85     }
 86     
 87     func hasRightChild(_ index:Int) -> Bool{
 88         return self.rightChildIndex(index) < self.count
 89     }
 90     
 91     func add(_ item:T){
 92         self.data.append(item)
 93         if self.data.count > 1{
 94             self.heapifyUp()
 95         }
 96     }
 97     
 98     func poll() -> T{
 99         let first = self.data[0]
100         self.data[0] = self.data[self.count - 1]
101         self.data.removeLast()
102         self.heapifyDown()
103         return first
104     }
105     
106     func peek() -> T?{
107         if self.count == 0{
108             return nil
109         }
110         return self.data[0]
111     }
112     
113     func heapifyUp(){
114         var currentIndex = self.count - 1
115         while hasParent(currentIndex) && parent(currentIndex) > self.data[currentIndex]{
116             self.data.swapAt(currentIndex, parentIndex(currentIndex))
117             currentIndex = parentIndex(currentIndex)
118         }
119     }
120     
121     func heapifyDown(){
122         var currentIndex = 0
123         while hasLeftChild(currentIndex){
124             var smallerIndex = leftChildIndex(currentIndex)
125             if hasRightChild(currentIndex) && rightChild(currentIndex) < leftChild(currentIndex){
126                 smallerIndex = rightChildIndex(currentIndex)
127             }
128             if self.data[currentIndex] > self.data[smallerIndex]{
129                 self.data.swapAt(currentIndex, smallerIndex)
130                 currentIndex = smallerIndex
131             }else{
132                 break
133             }
134         }
135     }
136     
137     var count:Int{
138         return self.data.count
139     }
140 }
141 
142 class NumberCount : Comparable{
143     
144     let n:Int
145     var count:Int = 0
146     
147     init(_ n:Int, _ count:Int){
148         self.n = n
149         self.count = count
150     }
151     
152     static func < (lhs:NumberCount, rhs:NumberCount) -> Bool{
153         return lhs.count < rhs.count
154     }
155     
156     static func == (lhs:NumberCount, rhs:NumberCount) -> Bool{
157         return lhs.count == rhs.count
158     }
159 }

推荐3（助力理解优先队列）：

  1 class Solution {
  2     struct MyTuple: Comparable {
  3         var first, second: Int
  4         static func < (lhs: MyTuple, rhs: MyTuple) -> Bool {
  5             return lhs.second < rhs.second
  6         }
  7     }
  8     func topKFrequent(_ nums: [Int], _ k: Int) -> [Int] {
  9         var dict: [Int: Int] = [:]
 10         for num in nums {
 11             if let val = dict[num] {
 12                 dict[num] = val + 1
 13             }
 14             else {
 15                 dict[num] = 1
 16             }
 17         }
 18 
 19         var heap: Heap<MyTuple> = Heap(isMaxHeap: false)
 20         for (key, value) in dict {
 21             if heap.count < k {
 22                 heap.insert(MyTuple(first: key, second: value))
 23             }
 24             else {
 25                 if value > heap.top()!.second {
 26                     heap.replace(MyTuple(first: key, second: value))
 27                 }
 28             }
 29         }
 30 
 31         var result: [Int] = []
 32         while !heap.isEmpty() {
 33             result.append(heap.delete()!.first)
 34         }
 35 
 36         return result.reversed()
 37     }
 38 }
 39 
 40 struct Heap<T: Comparable> {
 41     fileprivate var nums: [T?] = [Optional.none]
 42     fileprivate var isMaxHeap: Bool = true
 43     public var count: Int {
 44         return nums.count - 1
 45     }
 46     
 47     public init(_ arr: [T] = [], isMaxHeap: Bool = true) {
 48         self.isMaxHeap = isMaxHeap
 49         self.nums.append(contentsOf: arr)
 50         for i in stride(from: count/2, to: 0, by: -1) {
 51             isMaxHeap ? heapifyDown(i, &nums, >) : heapifyDown(i, &nums, <)
 52         }
 53     }
 54     
 55     // 是否为空
 56     public func isEmpty() -> Bool {
 57         return count == 0
 58     }
 59     
 60     // 插入元素
 61     public mutating func insert(_ num: T) {
 62         nums.append(num)
 63         heapify(count, &nums) { a, b in
 64             return self.isMaxHeap ? a > b : a < b
 65         }
 66     }
 67     
 68     // 删除堆顶元素
 69     public mutating func delete() -> T? {
 70         guard !isEmpty() else {
 71             return nil
 72         }
 73         //将堆顶元素与最后一个元素交换
 74         nums.swapAt(1, count)
 75         let res = nums.removeLast()
 76         heapifyDown(1, &nums) { a, b in
 77             return self.isMaxHeap ? a > b : a < b
 78         }
 79         return res
 80     }
 81     
 82     // 堆顶元素
 83     public func top() -> T? {
 84         guard !isEmpty() else {
 85             return nil
 86         }
 87         return nums[1]
 88     }
 89     
 90     // 替换堆顶元素
 91     public mutating func replace(_ num: T) {
 92         nums[1] = num
 93         isMaxHeap ? heapifyDown(1, &nums, >) : heapifyDown(1, &nums, <)
 94     }
 95     
 96     // 堆化(自下向上)
 97     private func heapify(_ location: Int, _ nums: inout [T?],  _ compare: (T, T) -> Bool) {
 98         var loc = location
 99         while loc/2 > 0 && compare(nums[loc]!, nums[loc/2]!) {
100             nums.swapAt(loc, loc/2)
101             loc /= 2
102         }
103     }
104     
105     // 堆化(自上而下)
106     fileprivate func heapifyDown(_ location: Int, _ nums: inout [T?], _ compare: (T, T) -> Bool) {
107         var loc = location
108         while loc * 2 <= count {
109             var swapLoc = loc
110              
                       
                    
                     
                      



鲜花




握手




雷人




路过




鸡蛋