Painless
OddOccurrencesInArray
奇数の要素で発生する値を見つけます。
タスクの説明
N個の整数で構成される空でない配列Aが与えられます。配列には奇数の要素が含まれており、配列の各要素は、ペアになっていない1つの要素を除いて、同じ値を持つ別の要素とペアにすることができます。
たとえば、配列Aでは次のようになります。
A [0] = 9 A [1] = 3 A [2] = 9
A [3] = 3 A [4] = 9 A [5] = 7
A [6] = 9
- インデックス0と2の要素の値は9です。
- インデックス1と3の要素の値は3です。
- インデックス4と6の要素の値は9です。
- インデックス5の要素の値は7であり、ペアになっていない。
関数を書く：
class Solution {public int solution（int [] A）; }
上記の条件を満たすN個の整数で構成される配列Aが与えられると、対になっていない要素の値を返します。
たとえば、次のような配列Aが与えられます。
A [0] = 9 A [1] = 3 A [2] = 9
A [3] = 3 A [4] = 9 A [5] = 7
A [6] = 9
上記の例で説明したように、関数は7を返す必要があります。
次の仮定のための効率的なアルゴリズムを記述します。
- Nは[1..1,000,000]の範囲内の奇数の整数です。
- 配列Aの各要素は、[1..1,000,000,000]の範囲内の整数です。
- Aの値の1つを除くすべてが、偶数回発生します。
解く
Detected time complexity:
O(N) or O(N*log(N))
Program
OddOccurrencesInArray.java
public int solution(int[] A) {
int goal = 0;
java.util.Arrays.sort(A);
for (int i = 0; i < A.length -1; i++) {
if (A[i] != A[i + 1]) {
goal = A[i];
break;
}
i++;
}
if (goal == 0) {
goal = A[A.length - 1];
}
return goal;
}
jUnit
OddOccurrencesInArrayTest.java
Report
Candidate Report: training66EE8T-EUB