Two common solutions for kth of sorted matrix with python


  • 0
    E

    Solution 1:min-heap

    import Queue
    class comp(object):
        def __init__(self,a,b,c):
            self.a,self.b,self.c=a,b,c
        def __cmp__(self,other):
            return cmp(self.a,other.a)
        def out(self):
            return (self.a,self.b,self.c)
    class Solution(object):
        def findKthNumber(self, m, n, k):
            q=Queue.PriorityQueue()
            for i in range(1,n+1):q.put(comp(1*i,1,i))
            while k>1:
                k-=1
                t=q.get().out()
                #print t[0]
                if t[1]>=m:continue
                #print (t[1]+1)*t[2]
                q.put(comp((t[1]+1)*t[2],t[1]+1,t[2]))
            return q.get().out()[0]
    

    Solution 2:binary search

    class Solution(object):
        def findKthNumber(self, m, n, k):
            st,en=1,m*n
            while st<en:
                mid=(st+en)>>1
                count=sum([min(mid/i,n) for i in range(1,m+1)])
                if count<k:st=mid+1
                else:en=mid
            return st
    

  • 0
    T

    min heap is probably TLE


Log in to reply
 

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