Posted at

【JavaScript】CodilityのLesson2-2解答例


背景

Codilityというプログラミング学習サイトのLesson2「OddOccurrencesInArray」を解いた


問題内容

「奇数個の要素を含む配列の中で、1度しか使われていない数値を求めよ」という問題。

例えば、A = [3, 9, 3, 7, 1, 9, 1]という配列が与えられた場合、答えは7となる。


サンプルコード(解答例)

※正しい答えは出力されるが、計算に時間がかかりすぎるため、完璧な解答ではない。

※また、es6の文法が混ざっていてよろしくない書き方になっている。

1. 配列Aのi番目とj番目(j = i + 1, i + 2, i + 3, ...)の要素を比較する。

2. i番目とj番目の要素が等しい数値であれば、それぞれの数値を0に置き換える。

3. 最後まで比較し終わったら、配列Aの要素は1つを除いてすべて0になっているので、配列Aの中から0でない数値を取り出し、それが答えとなる。

function solution(A) {

for (var i = 0; i < A.length; i++) {
for (var j = i + 1; j < A.length; j++) {
if (A[i] == A[j]) {
A[i] = 0;
A[j] = 0;
break;
}
}
}
var rslt = A.filter(item => item != 0); //Aから0である要素をすべて削除し新しい配列を作る
return rslt[0];
}


失敗したコード

else if (i != j && A[i] != A[j])で、配列中で1度も被らない数値を取得しようとした。

しかし、j = nのときに、A[i] != A[j]となりreslt = A[i]を得たとしても、

j = n + 1のときに、A[i] == A[j]となる場合がある。

この場合、A[i]は被っている数値なのに、答えとして扱われてしまうので間違い。

function solution(A) {

for (var i = 0; i < A.length; i++) {
for (var j = 0; j < A.length; j++) {
if (i != j && A[i] == A[j]) {
break;
} else if (i != j && A[i] != A[j]) {
var reslt = A[i];
}
}
}
return reslt;
}


感想

正しい答えは出力されるが計算に時間がかかりすぎていたり、ごちゃごちゃな文法で書いてしまっていたりと反省点が多い。

後日改めてしっかりとした解答を載せたいと考えています。

より良い解答などあれば、コメントに是非お願いします。