Python 7X% solution


  • 0

    Solution by my own. Welcome to any implements and questions.

    def __init__(self):
        self.l = {}
        self.dic = {}
        self.f = []
        
    def halfcompare(self,nums,d):
        if  len(d) == 0: return 0
        elif  nums < d[0]: return 0
        elif  nums > d[-1]: return len(d)
        s_t, a_f = 0, len(d) - 1
        while True:
            h_n = (s_t + a_f)/2
            if nums < d[h_n]: a_f = h_n
            else: s_t = h_n
            if s_t + 1 >= a_f: return (s_t + 1) if nums > d[s_t] else s_t
            
    def inc(self, key):
        if key not in self.dic:
            self.dic[key] = 1
            if self.dic[key] not in self.f: self.l[1] = [key]; self.f.insert(0,1)
            else: self.l[1].append(key)
        else:
            n = self.dic[key]
            self.dic[key] += 1
            if n + 1 not in self.f: self.l[n+1] = [key]; self.f.insert(self.halfcompare(n+1,self.f),n+1)
            else: self.l[n+1].append(key)
            del self.l[n][self.l[n].index(key)]
            if not self.l[n]: del self.f[self.halfcompare(n,self.f)]; del self.l[n];
        
    def dec(self, key):
        
        if key in self.dic:
            n = self.dic[key]
            self.dic[key] -= 1
            if n-1 >0:
                if n - 1 not in self.f: self.l[n-1] = [key]; self.f.insert(self.halfcompare(n-1,self.f),n-1)
                else: self.l[n-1].append(key)
            else:
                del self.dic[key]
            del self.l[n][self.l[n].index(key)]
            if not self.l[n]: del self.f[self.halfcompare(n,self.f)]; del self.l[n];
        
    def getMaxKey(self):
        if not self.f: return ''
        else: return self.l[self.f[-1]][0]
    
    def getMinKey(self):
        if not self.f: return ''
        else: return self.l[self.f[0]][0]

Log in to reply
 

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