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


  • 0
    H

    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
    }
    

Log in to reply
 

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