Lesson3のOddOccurencesInArrayの内容はリスト内のペアになっていないものを返すというものです。
例えば、[1,2,3,4,3,2,1]においてペアになっていないものは4だけです。
例えば、[1,1,1,3,1,1,1]においてペアになっていないものは1です。
例えば、[1,1,1,3,3,1,,1]においてペアになっていないものは1です。
さて、ペアでないものを見つける一番はやい方法はなんでしょうか。
それはまずは並び替えるということです。
[1,2,3,4,3,2,1]ならば[1,1,2,2,3,3,4]なので4
[1,1,1,3,1,1,1]ならば[1,1,1,1,1,1,3]なので3
[1,1,1,3,3,1,,1ならば[1,1,1,1,1,3,3]なので1
こうした方が見やすいですよね。
アルゴリズムは以下の通りです。
[アルゴリズム]
1.リストの数字を小さい順に並び替える
2.先頭から順番に、現在の要素と次の要素が等しければ、それがペアとなるので、次のペアを探していく。
3ペアとならないものを見つけたらその数字を返す。
具体的にコードを見ていきましょう。
def solution(A):
A = sorted(A)#Aをソートする
len_A = len(A)
i = 0
if len_A > 1:
while A[i] == A[i+1] and i < len_A: #ペアになっていない、あるいは配列の走査が終わったら終了
if i+2 == len_A-1: #リストの最後に答えがある場合にA[i]==A[i-1]のような比較対象がそもそもないためwhile文の処理が行えない
return A[i+2]
else:
i +=2
return A[i]
else:
return A[0] #リストが一個だけだった場合
さて結果は。。。。？
よかったです。処理速度についても
こんな感じ。
今回のように先にソートさせてから考える方が二重ループを回避でき、処理が早く済むということがある。メモメモ…