这就是用典型的用小顶堆思路来解决
class Solution {
func topKFrequent(_ nums: [Int], _ k: Int) -> [Int] {
let minQ = PriorityQueue<(Int, Int)>.init { arr1, arr2 in
return arr1.1 < arr2.1
}
let dict = nums.reduce(into: [:]) { partialResult, curVal in
partialResult[curVal, default: 0] += 1
}
for key in dict.keys {
let count = dict[key]!
if minQ.count < k {
minQ.push((key, count))
} else {
if minQ.peek()!.1 <= count {
minQ.poll()
minQ.push((key, count))
}
}
}
var arr = [Int]()
for (i,_) in minQ.elements {
arr.append(i)
}
return arr
}
}
typealias PriorityBlock = (T, T) -> Bool
class PriorityQueue {
var elements = [T]()
var count: Int {
return elements.count
}
var compartor: PriorityBlock
init(_ block: @escaping PriorityBlock) {
compartor = block
elements = [T]()
}
public func push(_ val: T) {
elements.append(val)
siftUp(count - 1)
}
// 看一眼堆顶元素是什么
public func peek() -> T? {
if count == 0 {
return nil
}
return elements.first!
}
// 拿出堆顶元素
public func poll() -> T? {
if count == 0 {
return nil
}
elements.swapAt(0, count - 1)
let ele = elements.removeLast()
siftDown(0)
return ele
}
// 上滤
private func siftUp(_ index: Int) {
guard index > 0 else { return }
let parent = (index - 1) / 2
if compartor(elements[index], elements[parent]) {
elements.swapAt(index, parent)
siftUp(parent)
}
}
// 下滤
private func siftDown(_ index: Int) {
var parent = index
let left = index * 2 + 1
let right = index * 2 + 2
if left < count && compartor(elements[left], elements[parent]) {
parent = left
}
if right < count && compartor(elements[right], elements[parent]) {
parent = right
}
if parent != index {
elements.swapAt(index, parent)
siftDown(parent)
}
}
}
Swfit封装的堆详解:
typealias PriorityBlock= (T, T) -> Bool class PriorityQueue { var elements = [T]() var count: Int { return elements.count } var compartor: PriorityBlock init(_ block: @escaping PriorityBlock ) { compartor = block elements = [T]() } public func push(_ val: T) { elements.append(val) siftUp(count - 1) } // 看一眼堆顶元素是什么 public func peek() -> T? { if count == 0 { return nil } return elements.first! } // 拿出堆顶元素 public func poll() -> T? { if count == 0 { return nil } elements.swapAt(0, count - 1) let ele = elements.removeLast() // 先把最后一个移除掉 siftDown(0) // 再进行下滤 return ele } // 上滤 private func siftUp(_ index: Int) { guard index > 0 else { return } let parent = (index - 1) / 2 // 小顶堆,小的值要在上面 if compartor(elements[index], elements[parent]) { // 当前位置和父节点位置比较,如果比父节点位置的值小,就交换 elements.swapAt(index, parent) siftUp(parent) } } // 下滤 private func siftDown(_ index: Int) { var parent = index let left = index * 2 + 1 let right = index * 2 + 2 if left < count && compartor(elements[left], elements[parent]) { // 如果左边的比父节点值小,就交换,父节点就准备下沉到左边去 parent = left } if right < count && compartor(elements[right], elements[parent]) { // 如果右边比左边的值更小,就交换,让父节点沉到右边去 parent = right } if parent != index { elements.swapAt(index, parent) siftDown(parent) } } }



