# Scala using PriorityQueue with O(m+k*log(m)) time (m: unique element)

• Class kv(key-value) is for building the MaxHeap. While building the MaxHeap, we use index:Map[Int,Int] to record the index a number is in the num[kv].
If scala map can apply(key) at O(1) time, the overall time complexity is O(m+k*log(m)) with m is the number of the unique elements

def topKFrequent(nums: Array[Int], k: Int): List[Int] = {
val index = collection.mutable.Map[Int, Int]()
val num = Array.fill(nums. length){ new kv(0,0) }
var difnum=0
for(n<-nums){
if(index contains n){
num(index.apply(n)).incr
}else{
index += (n -> difnum)
num(difnum).replace(n,1)
difnum = difnum + 1
}
}

val minHeap = scala.collection.mutable.PriorityQueue.empty(MinOrder)
for(kvele<- num)    minHeap += kvele
(for(kk<-1 to k) yield minHeap.dequeue.key).toList
}
class kv(var key: Int, var value: Int){
def replace(k: Int, v: Int){
key=k
value=v
}
def incr{
value = value+1
}
}
object MinOrder extends Ordering[kv](){
def compare(x:kv, y:kv) = x.value compare y.value
}

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.