这个函数是 O(N+M) 还是 O(N*M)？

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() 循环 A N 次，然后循环结果 M 次，因此 N+M 次。 然而网上测试说是N*M，把我难住了。

It is O(M + N);这里没有嵌套循环。这可以减少数量较多的成本；渐近地，较小的循环并不重要，使得O(N).

首先你循环A元素（N迭代），然后分别循环M元素。