Codility 2.2 Odd occurrences in array

5988 ワード
codility algorithm テキストリンク
質問する
  • Odd occurrences in array
  • 個の与えられた奇数個の整数からなる配列Aがある.この列には2つの整数が1対になっている.
  • 奇数個なので、ペア2個ごとにペアリングすると数が残ります.この数を返す問題です.
  • 2Aを構成する整数には、重複する値もある.
  • Aが{9,3,9,3,9,7,9}なら、答えは7です.
    • に答える
    しょきかいほう
  • は、Aを配列し、java.utils.Arraysモジュールを使用して並べ替えられる.
    • 2サイクル当たり
  • 2A、比較iおよびi+1次元素
    2.1が異なる場合は2つなのでi回の値を返します.
  • 配列が奇数の場合、最後の値は決定されません.したがって、巡回が終了すると、Aの最後の値が返される.
    • XORの使用
  • XOR演算を用いてO(N)内で問題を解決することもできる.
    -2つのビットが同じ場合は0を返し、異なる場合は1を返します.
  • 0に基づいてすべての要素をXOR演算すると、同じ数は最終的にゼロに消去され、ペアリングされていない数が1つしか残っていません.
    • コード#コード#
    並べ替え後に2回遍歴する方法
    import java.util.Arrays;

class Solution {
    public int solution(int[] A) {
        Arrays.sort(A);

        if (A.length < 2) {
            return A[0];
        }

        for(int ii = 0; ii < A.length - 1; ii += 2) {
            if (A[ii] != A[ii + 1]) {
                return A[ii];
            }
        }

        return A[A.length - 1];
    }
}
    XOR操作の使用方法
    class Solution {
    public int solution(int[] A) {
        int sum = 0;
        
        for (int el : A) {
            sum = sum ^ el;
        }

        return sum;
    }
}
    210317-47日目
    GitとGitHubとは?