[Codility] MaxCounters




77%


効率-2:カウンタアレイの初期化にも時間がかかります
def solution(N, A):
    counters = [0] * N
    m = 0

    for a in A:
        if a > N:
            counters = [m]*N
        else:
            counters[a-1] += 1
            m=max(counters[a-1], m)
    
    if isNup :
        for i, c in enumerate(counters):
            if c < curMax:
                counters[i] = curMax
    return counters

100%


カウンタアレイの初期化を最小化!
更新
  • 現在のMax値
  • 反復文(A lookup)では、現在のMax値より小さい値がある場合は現在のMax値に変更し、+1
  • 増加
  • 反復文が終了すると、すべてのカウンタが表示され、現在のMax値より小さい値が更新されます.現在のMax値は更新されますが、A look up反復文は過去の値を更新しません.したがって、最終的な一括更新は時間の複雑さを軽減します.
  • def solution(N, A):
        counters = [0] * N
        isNup = False
        m = 0
        curMax = 0
    
        for a in A:
            if a > N:
                isNup = True
                curMax = m
            else:
                if counters[a-1] < curMax :
                    counters[a-1] = curMax
                counters[a-1] += 1
                m=max(counters[a-1], m)
        
        if isNup :
            for i, c in enumerate(counters):
                if c < curMax:
                    counters[i] = curMax
        return counters