★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★

➤微信公众号：山青咏芝（shanqingyongzhi）

➤博客园地址：山青咏芝（）

➤GitHub地址：

➤原文地址：  

➤如果链接不是山青咏芝的博客园地址，则可能是爬取作者的文章。

➤原文已修改更新！强烈建议点击原文地址阅读！支持作者！支持原创！

★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★

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

Example 1:

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

Example 2:

Input: nums = [1], k = 1Output: [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
     
       {  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
      
       (_ 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     @discardableResult105     public mutating func remove() -> T? {106         guard !nodes.isEmpty else {107             return nil108         }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 value116         }117     }118     119     @discardableResult120     public mutating func remove(at index: Int) -> T? {121         guard index < nodes.count else { return nil}122         let size = nodes.count - 1123         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 nodes137     }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 in145             return f.1 < s.1146         }147         var dict = [Int: Int]()148         for i in nums {149             dict[i] = (dict[i] ?? 0) + 1150         }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
     
      ([])  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
      
       { 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 first104     }105     106     func peek() -> T?{107         if self.count == 0{108             return nil109         }110         return self.data[0]111     }112     113     func heapifyUp(){114         var currentIndex = self.count - 1115         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 = 0123         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 = smallerIndex131             }else{132                 break133             }134         }135     }136     137     var count:Int{138         return self.data.count139     }140 }141 142 class NumberCount : Comparable{143     144     let n:Int145     var count:Int = 0146     147     init(_ n:Int, _ count:Int){148         self.n = n149         self.count = count150     }151     152     static func < (lhs:NumberCount, rhs:NumberCount) -> Bool{153         return lhs.count < rhs.count154     }155     156     static func == (lhs:NumberCount, rhs:NumberCount) -> Bool{157         return lhs.count == rhs.count158     }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
     
       = 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
      
        { 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 /= 2102         }103     }104     105     // 堆化(自上而下)106     fileprivate func heapifyDown(_ location: Int, _ nums: inout [T?], _ compare: (T, T) -> Bool) {107         var loc = location108         while loc * 2 <= count {109             var swapLoc = loc110             if compare(nums[loc * 2]!, nums[loc]!) {111                 swapLoc = loc * 2112             }113             if loc * 2 + 1 <= count && compare(nums[loc * 2 + 1]!, nums[swapLoc]!) {114                 swapLoc = loc * 2 + 1115             }116             if loc == swapLoc {117                 break118             }119             nums.swapAt(loc, swapLoc)120             loc = swapLoc121         }122     }123 }
      
     

---

 92ms

1 class Solution { 2     func topKFrequent(_ nums: [Int], _ k: Int) -> [Int] { 3         if nums == [] { return [] } 4         var map = [Int : Int]() 5          6         // O(n) 7         for i in 0...nums.count-1 { 8             if let m = map[nums[i]] { 9                 // O(1)?10                 map.updateValue(m + 1, forKey: nums[i])11             }12             else{13                 map[nums[i]] = 114             }15         }16         17         // sortedBy is O(n log n)18         var mapVal = map.sorted(by: { $0.value > $1.value })19         var res = [Int]()20         21         // O(k)22         for i in 0...k-1 {23             res.append(mapVal[i].key)24         }25         26         return res27     }28 }

---

96ms

1 class Solution { 2     func topKFrequent(_ nums: [Int], _ k: Int) -> [Int] { 3  4         var countDict = [Int: Int]() 5          6         for n in nums { 7             countDict[n, default: 0] += 1 8         } 9         10         var sorted = countDict.sorted { $0.value > $1.value }11         12         return sorted[0..

---

100ms

1 class Solution { 2     func topKFrequent(_ nums: [Int], _ k: Int) -> [Int] { 3         guard nums.count > 1 else { return nums } 4          5         var hashMap: [Int: Int] = [:] 6          7         for i in nums { 8             hashMap[i, default: 0] +=  1  9         }10         11         let sortedPairs = hashMap.sorted{ $0.value > $1.value}12         13         let sortedKeys = sortedPairs.map{ $0.key }14      15         return Array(sortedKeys.prefix(k))16     }17 }

---

104ms

1 class Solution { 2     func topKFrequent(_ nums: [Int], _ k: Int) -> [Int] { 3          4         var res = [Int]() 5         var map = [Int:Int]() 6         if k > nums.count { return res } 7          8         for num in nums { 9             map[num] = map[num] == nil ? 1 : map[num]! + 110         }11         12         let sortedArray = map.sorted{ $0.value > $1.value }13         var count = 014         for (key, value) in sortedArray {15         if(count >= k) { break }16             res.append(key)17             count += 1 18         }19         return res20     }21 }

---

108ms

1 class Solution {2     func topKFrequent(_ nums: [Int], _ k: Int) -> [Int] {3         let counter: [Int: Int] = nums.reduce(into: [Int: Int]()) { $0[$1, default: 0] += 1}4         let sortedKeys = counter.keys.sorted { counter[$0]! >= counter[$1]!}5         return [Int](sortedKeys[0..

---

112ms

1 class Solution { 2     func topKFrequent(_ nums: [Int], _ k: Int) -> [Int] { 3         var countMap: [Int: Int] = [:] 4         for num in nums { 5             countMap[num, default: 0] += 1 6         } 7          8         var sortedList: [[Int]] = Array(repeating: [], count: nums.count + 1) 9         for (key, value) in countMap {10             sortedList[value].append(key) 11         }12         13         var result: [Int] = []14         var i = nums.count15         while i > 0 && result.count < k {16             result.append(contentsOf: sortedList[i])17             18             i -= 119         }20         return result21     }22 }

---

120ms

1 class Solution { 2     func topKFrequent(_ nums: [Int], _ k: Int) -> [Int] { 3     var dict = [Int:Int]() 4     nums.forEach { 5         dict[$0] = (dict[$0] == nil ? 0 : dict[$0]! ) + 1 6     } 7   8     return dict.sorted(by:  { $0.value > $1.value } )[0..

---

124ms

1 class Solution { 2     func topKFrequent(_ nums: [Int], _ k: Int) -> [Int] { 3         var countMap:[Int:Int] = [:] 4         for num in nums { 5             countMap[num] = countMap[num] == nil ? 1 : countMap[num]! + 1 6         } 7         var vals = Array(countMap.keys) 8         vals.sort { 9             return countMap[$0]! > countMap[$1]!10         }11         return Array(vals[0..

---

148ms

1 class Solution { 2     func topKFrequent(_ nums: [Int], _ k: Int) -> [Int] { 3         //  input: [1, 1, 1, 2, 2, 3, 3, 3, 4, 4, 4,] 4         //  buckets: [[], [], [2], [1, 4, 3], [], [], [], [], [], [], [], []] 5         // list of numbers whose frequency is at buckets[i] 6         var buckets = Array(repeating: [Int](), count: nums.count + 1) 7          8         // key: number      value: number of times it appears in the array 9         var freqMap = [Int: Int]()10         11         for num in nums {12             if let times = freqMap[num] {13                 freqMap[num] = 1 + times14             } else {15                 freqMap[num] = 116             }17         }18 19         for key in freqMap.keys {20             let frequency = freqMap[key]!21             buckets[frequency].append(key)22         }23         24         print(buckets)25 26         // we go backwards because the end contains the highest frequencies27         var result = [Int]()28         for i in stride(from: buckets.count - 1, to: 0, by: -1) {29             if !buckets[i].isEmpty && result.count < k {30                 result.append(contentsOf: buckets[i])31             }32         }33         return result34     }35 }

---

156ms

1 class Solution { 2     func topKFrequent(_ nums: [Int], _ k: Int) -> [Int] { 3         var temp = (Dictionary(nums.map { ($0, 1) }, uniquingKeysWith: +)).sorted { (a, b) -> Bool in 4             return a.value>b.value 5             }.compactMap { (a) -> Int? in 6                 return a.key 7         } 8         return Array(temp[0..

---

160ms

1 class Solution { 2     func topKFrequent(_ nums: [Int], _ k: Int) -> [Int] { 3          4         // Map for value -> # occurences 5         var dict = [Int: Int]() 6         for value in nums { 7             dict[value] = (dict[value] ?? 0) + 1 8         } 9         10         print(dict)11         12         // Index maps to frequency the value appears in array13         var buckets = [[Int]](repeating: [], count: nums.count + 1)14         for (key, value) in dict {15             buckets[value].append(key)16         }17         18         print(buckets)19         20         var kMostFrequent = [Int]()21         var currMost = 022         23         for subArr in buckets.reversed() where currMost < k {24             for value in subArr where currMost < k {25                 kMostFrequent.append(value)26                 currMost += 127             }28         }29         30         return kMostFrequent31     }32 }

---

164ms

1 class Solution { 2     func topKFrequent(_ nums: [Int], _ k: Int) -> [Int] { 3         if k < 0 || k > nums.count { return [] } 4         var dict = [Int: Int]() 5         nums.forEach { 6             dict[$0] = (dict[$0] ?? 0) + 1 7         } 8          9         var pairs = dict.map { $0 }10         quickSelect(&pairs, 0, pairs.count - 1, k)11         return Array(pairs.prefix(k).map { $0.key })12     }13     14     func quickSelect(_ pairs: inout [(key: Int, value: Int)], _ start: Int, _ end: Int, _ k: Int) {15         16         if start == end {17             return 18         }19         20         let pivot = pairs[end]21         var left = start22         for i in start..
     
      = pivot.value {24                 pairs.swapAt(left, i)25                 left += 126             }27         }28         pairs.swapAt(left, end)29         30         if left + 1 == k {31             return 32         } else if left + 1 > k {33             quickSelect(&pairs, start, end - 1, k)34         } else {35             quickSelect(&pairs, left + 1, end, k)36         }37     }38 }
     

---

172ms

1 class Solution { 2     func topKFrequent(_ nums: [Int], _ k: Int) -> [Int] { 3         guard k >= 1 && k <= nums.count else { 4             return [] 5         } 6         var numCounts = [Int: Int]() 7         for num in nums { 8             if let numCount = numCounts[num] { 9                 numCounts[num] = numCount + 110             } else {11                 numCounts[num] = 112             }13         }14         let numInfos = numCounts.sorted {15             $0.1 >= $1.116         }17         return Array(numInfos[0 ..< k]).map {18             $0.019         }20     }21 }