OddOccurrencesInArray:
Find value that occurs in odd number of elements.

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.

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:

class Solution { public int solution(int[] A); }

that, given an array A consisting of N integers fulfilling the above conditions, returns the value of the unpaired element.

For example, given 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 function should return 7, as explained in the example above.

Write an efficient algorithm for the following assumptions:

  • N is an odd integer within the range [1..1,000,000];
  • each element of array A is an integer within the range [1..1,000,000,000];
  • all but one of the values in A occur an even number of times.

這題一開始想法有點錯誤，跑了兩個版本的雙迴圈…取第一個出來比對到最後，再取第二個出來比對到最後…

第一個版本

public static int oddOccurrencesInArray(int[] a) {
        Set<Integer> set = new HashSet<>();
        for (int i = 0; i < a.length; i++) {
            if (set.contains(i)) {
                continue;
            } else if (i == a.length - 1) {
                return a[i];
            }
            for (int j = i + 1; j < a.length; j++) {
                if (a[i] == a[j]) {
                    set.add(j);
                    break;
                }
                if (j == a.length - 1) {
                    return a[i];
                }
            }
        }
        return -1;
    }

第二個版本

    public static int oddOccurrencesInArray(int[] a) {
        Set<Integer> set = new HashSet<>();
        for (int i = 0, j = i + 1; i < a.length; j++) {
            if (set.contains(i)) {
                i++;
                continue;
            }
            if (j <= a.length - 1 && a[i] == a[j]) {
                set.add(j);
                i++;
                j = i;
            } else if (j == a.length - 1 || i == a.length - 1) {
                return a[i];
            }
        }
        return -1;
    }

後來效能都很差，才想到其實跑一次迴圈就好了，相同的數字不要，剩下的就是沒有匹配到的數字，我用一個set去放數字，判斷如容器內有包含此數字則移除，最後用疊代器取出值回傳。

public static int oddOccurrencesInArray(int[] a) {
        Set<Integer> set = new HashSet<>();
        for (int j : a) {
            if (set.contains(j)) {
                set.remove(j);
            } else {
                set.add(j);
            }
        }
        return set.iterator().next();
    }

後來看到有更快速的寫法…使用xor加總後就是結果…真是厲害!

public static int oddOccurrencesInArray(int[] a) {
        int result = 0;
        for (int j : a) {
            result ^= j;
        }
        return result;
    }