Lesson2は問題が二つありました。
OddOccurrencesInArray
オカレンシスの意味を調べたら、発生って意味みたいです。「配列での奇数の発生」？よくわかりません。
とりあえず問題文を見てみましょう。
A non-empty array A consisting of N integers is given. The array contains an odd number of elements, and each element of the array can be paired with another element that has the same value, except for one element that is left unpaired.
空ではない、Nこの整数で構成された配列がある。配列は奇数の要素を持っている。一つの要素を除いて、それぞれの要素は同じ値を持つ違う要素と対になっている。
For example, in array A such that:
A[0] = 9
A[1] = 3
A[2] = 9
A[3] = 3
A[4] = 9
A[5] = 7
A[6] = 9
- the elements at indexes 0 and 2 have value 9,
- the elements at indexes 1 and 3 have value 3,
- the elements at indexes 4 and 6 have value 9,
- the element at index 5 has value 7 and is unpaired.
この場合は０番目と２番目が９、１番目と３番目が３、４番目と９番目が９、５番目が７で５番目が対になっていない。
Write a function that given an array A consisting of N integers fulfilling the above conditions, returns the value of the unpaired element.
「この条件を満たす、整数で構成された配列Aを与えられたとき、対になってない要素の値を返す関数を書きなさい」
def solution(A):
# write your code in Python 3.6
n_A = len(A)
answer = None
for i in range(n_A):
count = 0
for l in range(i):
if A[i] == A[l]:
count += 1
for l in range(i+1, n_A):
if A[i] == A[l]:
count += 1
if count%2 == 0:
answer = A[i]
return answer
こんな感じに回答しましたが５５点でした。
要素数が2000を超える場合はタイムアウトになってしまうみたいで、試しに手元の環境で実行したら２万1要素で１分くらいかかりました。
それくらい別にいいじゃんと思いましたが、こういうことにこだわって実行時間を削るのがプロの仕事なのかもしれません。
研究室でも実行時間が長い処理を行ってますが、とりあえず実行できることが最優先で、処理の速さはそこまで気にしてませんね。
しょうがないので、正解を調べてみるとこんな感じでした。
def solution(A)
if len(A) == 1:
return A[0]
A = sorted(A)
for i in range(0 , len (A) , 2):
if i+1 == len(A):
return A[i]
if A[i] != A[i+1]:
return A[i]
ソートして隣り合う偶数番目と奇数番目を比較すればいいんですね。
これなら、全部の数をいちいち参照する必要はないので簡単ですね。スマート！
本番でこういう工夫はできなそうです。
それでは。
