[Codility] MaxCount (python3)

https://app.codility.com/programmers/lessons/4-counting_elements/max_counters/
与えられたアレイAの要素の値に基づいて、与えられたN個のカウンタが作成され、返される問題.
Aの元素X
1<=X<=Nの場合、K個のカウンタ+1
X=N+1の場合、すべてのカウンタを現在の最大カウンタに変更します.
簡単に言えば、二重forゲートで解くことができますが、元素の最大個数は10万個なので、二重砲口で解くと効率的に失敗します.だからできるだけ繰り返し文の内部の繰り返し文を避けて、一回の繰り返し文と繰り返し文の外の論理で問題を解決します.

私の最初の答え

各複文はカウンタリストの最大値を求めtemp変数に格納する.
また,二重砲口を避けるためには,砲口のX=N+1を迂回する必要がある場合に最小値を記憶し,繰返し文終了後に相応の値を加算する.

def solution(N, A):
    # write your code in Python 3.6

    counter_list = [0] * N
    temp_max = 0
    min_in_list = 0
    for i in range(len(A)):
        if A[i] <= N:
            if counter_list[A[i]-1]  > min_in_list:
                counter_list[A[i]-1] += 1 # 그냥 +1
            else:
                counter_list[A[i]-1] = min_in_list + 1 # 최소값 +1

            temp_max = max(counter_list)    
        elif A[i] == N+1:
            min_in_list = temp_max

    for j in range(N):
        if counter_list[j] < min_in_list:
            counter_list[j] = min_in_list
     
    return counter_list
    pass

正解率は66%だった.もう少し時間を短縮せざるを得ない.pythonのmax()関数の時間複雑度はO(N)である.N個のカウンタリストをM回繰り返すfor文の内部で使用し,時間的複雑度はO(M*N)である.
少なくともこの関数を使用するか使用しないかの方法を見つけるべきだと思います.

私の2番目の答え

各反復文の最大値は求めず,X=N+1のときのみmin値を求め代入する.

def solution(N, A):
     # write your code in Python 3.6
    
    counter_list = [0] * N
    temp_max = 0
    min_in_list = 0
    for i in range(len(A)):
        if A[i] <= N:
            if counter_list[A[i]-1]  > min_in_list:
                counter_list[A[i]-1] += 1
            else:
                counter_list[A[i]-1] = temp_max + 1
        elif A[i] == N+1:
            temp_max = max(counter_list)
            min_in_list = temp_max

    for j in range(N):
        if counter_list[j] < min_in_list:
            counter_list[j] = min_in_list
       
    return counter_list

    pass

やはり正解率は66%max()ではなく、最大値を検索します.

私の3番目の答え

最初の方法と同様に、繰り返し文ごとに最大値が検索されます。ただし,max()メソッドではなくtemp値と比較するメソッドを用いて最大値を求める. def solution(N, A): # write your code in Python 3.6 counter_list = [0] * N temp_max = 0 min_in_list = 0 for i in range(len(A)): if A[i] <= N: if counter_list[A[i]-1] > min_in_list: counter_list[A[i]-1] += 1 else: counter_list[A[i]-1] = min_in_list + 1 if counter_list[A[i]-1] > temp_max: temp_max = counter_list[A[i]-1] elif A[i] == N+1: min_in_list = temp_max for j in range(N): if counter_list[j] < min_in_list: counter_list[j] = min_in_list return counter_list pass 結果はO(N+M)が正しい 効率の問題は思ったより難しいからです。次回からこのような質問に直面して、上のカットのようにゆっくりと解答を描いていけば助かります。