[PYTHON] Complexité du temps de leçon de codilité et mémo de réponse

Task: Maxcounters C'est une impression individuelle.

①Speed N*M

def solution(N, A):
    anslist = [0] * N
    maxvalue = 0
    for i in A:
        try:
            anslist[i-1] += 1
        except:
            maxvalue = max(anslist)
            anslist = [maxvalue] * N
    return anslist

Impressions et apprentissage

Je pensais que si je faisais le maximum à chaque essai, ce serait N * 2, donc J'ai essayé de maximiser uniquement lorsque cela était nécessaire. Mais, bien sûr, cela dépend de la fréquence d'apparition de N + 1, donc ce sera N * M. Convaincu.

②Speed: N+M

def solution(N, A):
    anslist = [0] * N
    maxchecker = 0
    for i in A:
        try:
            anslist[i-1] += 1
            if anslist[i-1] > maxchecker:
                maxchecker = anslist[i-1]
        except:
            anslist = [maxchecker] * N
    return anslist

Impressions et apprentissage: je ne sais pas pourquoi N ** + M ** ??? .. .. Suspect. Et je n'ai pas atteint la vitesse N ou Log (N).