python beats 100%


  • 0
    E

    Tn=O(n^2),Pn=O(n)

    def largestDivisibleSubset(self, nums):
        """
        :type nums: List[int]
        :rtype: List[int]
        """
        if nums==[]:return []
        nums.sort()
        dp,tables,f=[],{},True
        for n in nums:
            if f:dp.append([n]);tables[n]=-1;f=not f
            else:
                i=len(dp)-1
                while i>=0:
                    f2=False
                    for m in dp[i]:
                        if n%m==0:
                            f2=True
                            if i==len(dp)-1:dp.append([n])
                            else:dp[i+1].append(n)
                            tables[n]=m
                            break
                    if f2:break
                    i-=1
                else:
                    dp[0].append(n);tables[n]=-1
        a,res=dp[-1][0],[dp[-1][0]]
        while tables[a]!=-1:
            a=tables[a]
            res=[a]+res
        return res
    

Log in to reply
 

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