[Codility] 8. Leader

Leader of sequence

長さNの数列において、N/2以上の数が等しい要素が存在する場合、その値をleader of sequenceまたはleaderと呼ぶ.

例えば1)[6,8,4,6,8,6,6],leader=6である.(図)
例2)[1,2,3,4,5,6,7]ではリーダーは存在しない.
では、指導者をどう救うのか.現在考えられている素朴な方法はO(N 2)O(N^2)O(N 2)ですべての方法を探索することである.でもあまりにも非効率的

方法ツールバーの

(数列のすべての数が非負の数であると仮定します.)
リーダーはN/2個よりも多く存在するので、数列を並べ替え、中央値は当然リーダーの数に等しい.これはそれを利用したアルゴリズムです.

の数列を並べます.O(NlogN)
1.1ソート後の数列の中央値がリーダー候補となる.

候補の価値がn/2候補より大きい場合、候補はリーダーになる.O(N)

def find_leader(L):
	N = len(L)
    leader = -1 # leader가 없다면 -1을 return
    L.sort()    # sorting - O(NlogN)
    candidate = L[N // 2] # 중앙값은 leader의 후보
    count = 0   # 후보값의 개수
    
    # linear search - O(N)
    # 후보값이 수열에 몇개 존재하는지 counting
    for i in range(N):
    	if L[i] == candidate:
        	count += 1
    
    # 후보값이 N/2개 보다 많다면 leader이다.
    if count > N // 2:
    	leader = candidate
    
    return leader

方法スタック

(数列のすべての数が非負の数であると仮定します.)
リーダーは最も存在する数です.また、2つの異なる数を削除すると、残りのN−2個の数列のリーダーは同じリーダーを有する.なぜなら,削除した2つの数のうち1つがリーダーであっても,残りのN−2個の数列ではリーダーは(N−2)/2個よりもずっと存在するからである.
では、2つの異なる数字をどうやって消すのでしょうか->スタック!

スタックに順次プッシュします.

スタックの上部の2つの数を比較します.
2.1 2つの数が異なる場合、2つともスタックから削除されます.

def find_leader(L):
	N = len(L)
    size = 0
    for i in range(N):
    	# 스택이 비어있다면, value: top of the stack
    	if size == 0:
        	size += 1
            	value = L[i]
        else:
        	# 스택이 비어있지 않고, top과 현재 수가 다르면
           	# 현재 수를 스택에 넣지안고, top을 제거
        	if value != L[i]:
            	size -= 1
           	
            	# 스택에 현재 수 삽입
            	else:
            	size += 1
	
    candidate = -1
    leader = -1
    count = 0
    
    # 서로다른 쌍 제거후에도 스택이 남아있다면, top이 후보값
    if size > 0:
    	candidate = value  
    
    # 후보값이 N/2개보다 많은지 확인
    for i in range(N):
    	if L[i] == candidate:
        	count += 1
    if count > N // 2:
    	leader = candidate
    
    return leader