★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★➤微信公众号：山青咏芝（shanqingyongzhi）➤博客园地址：山青咏芝（https://www.cnblogs.com/strengthen/）➤GitHub地址：https://github.com/strengthen/LeetCode➤原文地址： https://www.cnblogs.com/strengthen/p/10740914.html ➤如果链接不是山青咏芝的博客园地址，则可能是爬取作者的文章。➤原文已修改更新！强烈建议点击原文地址阅读！支持作者！支持原创！★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★
Given a non-empty array of integers, return the k most frequent elements.
Example 1:
Input: nums = [1,1,1,2,2,3], k = 2 Output: [1,2]Example 2:
Input: nums = [1], k = 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 if compare(nums[loc * 2]!, nums[loc]!) { 111 swapLoc = loc * 2 112 } 113 if loc * 2 + 1 <= count && compare(nums[loc * 2 + 1]!, nums[swapLoc]!) { 114 swapLoc = loc * 2 + 1 115 } 116 if loc == swapLoc { 117 break 118 } 119 nums.swapAt(loc, swapLoc) 120 loc = swapLoc 121 } 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]] = 1 14 } 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 res 27 } 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..<k].map { $0.key } 13 } 14 }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]! + 1 10 } 11 12 let sortedArray = map.sorted{ $0.value > $1.value } 13 var count = 0 14 for (key, value) in sortedArray { 15 if(count >= k) { break } 16 res.append(key) 17 count += 1 18 } 19 return res 20 } 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..<k]) 6 } 7 }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.count 15 while i > 0 && result.count < k { 16 result.append(contentsOf: sortedList[i]) 17 18 i -= 1 19 } 20 return result 21 } 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..<k].map({$0.key}) 9 } 10 }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..<k]) 12 } 13 }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 + times 14 } else { 15 freqMap[num] = 1 16 } 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 frequencies 27 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 result 34 } 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..<k]) 9 } 10 }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 array 13 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 = 0 22 23 for subArr in buckets.reversed() where currMost < k { 24 for value in subArr where currMost < k { 25 kMostFrequent.append(value) 26 currMost += 1 27 } 28 } 29 30 return kMostFrequent 31 } 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 = start 22 for i in start..<end { 23 if pairs[i].value >= pivot.value { 24 pairs.swapAt(left, i) 25 left += 1 26 } 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 + 1 10 } else { 11 numCounts[num] = 1 12 } 13 } 14 let numInfos = numCounts.sorted { 15 $0.1 >= $1.1 16 } 17 return Array(numInfos[0 ..< k]).map { 18 $0.0 19 } 20 } 21 }
转载于:https://www.cnblogs.com/strengthen/p/10740914.html
