4 
def solution(M, A):
    result = [0] * M
    maxCount = 0
    setAll = 0

    for i in range(0,len(A)):
        if (A[i] == M + 1):
            setAll += maxCount
            maxCount = 0
            result = [0] * M
        else:
            result[A[i] - 1] += 1

            if (result[A[i] - 1] > maxCount):
                maxCount = result[A[i] - 1]

    for j in range(0,len(result)):
        result[j] += setAll

    return result


A = [ 1, 1, 1, 1, 2, 3] 
M = 2

print solution(M, A) # result = [ 4, 4 ]


A = [ 1, 2, 2, 4, 1, 1] 
M = 3

print solution(M, A) # result = [ 4, 2, 2 ]

私の計算では、solution() は AN 回ループし、ループ結果は M 回、つまり N+M になります。しかし、オンライン テストでは、代わりに N*M と表示され、困惑しました。

4

2 に答える 2

6

それはO(M + N); ここにはネストされたループはありません。これは、より大きな数のコストに減らすことができます。漸近的には、小さい方のループは問題にならず、 になりますO(N)。

最初にA要素をループ (N反復) し、次に個別にM要素をループします。

于 2013-11-09T17:21:45.813 に答える
5

これはO(N)、N + M特定の入力に対してループがあるためN, Mです。N最も重要な項のみを使用するため、時間の複雑さのために、これは 2 つのうちの大きい方 ( としましょう) に縮小されます。O(N*M)2 番目のループが最初のループ内にネストされている場合です。

于 2013-11-09T17:23:05.717 に答える