0
Help us understand the problem. What are the problem?

posted at

Codility lesson2 OddOccurencesInArray

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] #リストが一個だけだった場合

さて結果は。。。。?
スクリーンショット 2022-06-12 0.50.10.png

よかったです。処理速度についても
スクリーンショット 2022-06-12 2.06.15.png

こんな感じ。
今回のように先にソートさせてから考える方が二重ループを回避でき、処理が早く済むということがある。メモメモ…

Register as a new user and use Qiita more conveniently

  1. You can follow users and tags
  2. you can stock useful information
  3. You can make editorial suggestions for articles
What you can do with signing up
0
Help us understand the problem. What are the problem?