Блог

всем привет, мне было интересно, может ли кто-нибудь помочь мне понять временную и пространственную сложность этого решения для кода 1152 https://leetcode.com/problems/analyze-user-website-visit-pattern/ Проанализируйте Шаблон Посещения Веб-Сайта Пользователем. Я чувствую, что пространственная сложность равна O(N), где N-длина каждого списка в аргументах, а временная сложность равна O(N^4). Будет ли сложность пространства также зависеть от того, сколько существует последовательностей длины?

 class Solution:
    def mostVisitedPattern(self, username: List[str], timestamp: List[int], website: List[str]) -> List[str]:
        dic = {}
        seq ={}
        
        for i in range(len(username)):
            user = username[i]
            if user in dic:
                dic[user].append([timestamp[i], website[i]])
            else:
                dic[user] = [[timestamp[i], website[i]]]
        d = {}
        for key in dic:
            d[key] = {}
            l = dic[key]
            if len(l) >= 3:
                l.sort(key = lambda x:  x[0])
            for i in range(len(l)):
                for j in range(i 1, len(l)):
                    for k in range(j 1, len(l)):
                        s = l[i][1]   " "   l[j][1]   " "   l[k][1]
                        if s not in d[key]:
                            d[key][s] = 1
        c = 0
        max = ""
        for key in d:
            for k in d[key]:
                if k not in seq:
                    seq[k] =1
                else:
                    seq[k]  = 1
        for key in seq:
            if seq[key] > c:
                max = key
                c = seq[key]
            if seq[key] == c:
                if key < max:
                    max = key
                    c = seq[key] 
        return max.split(" ")