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

  • 0

    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
            if(index contains n){
                index += (n -> difnum)
                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){
        def incr{
            value = value+1
    object MinOrder extends Ordering[kv](){
        def compare(x:kv, y:kv) = x.value compare y.value

Log in to reply

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