题解 | #出现一次的数字#

题目

现在有一个整数类型的数组，数组中素只有一个元素只出现一次，其余的元素都出现两次。

思路

一、排序比较

• 排序后的数组，相同的元素必定相邻。

• 如果一个元素与前后元素的不相等（除开 首项和尾项），那么这个元素就是目标。

• 数组的 首项和尾项 需要单独比较，在最后。

二、异或计算

• 1、相同的数字异或（^）结果为：0。

• 所有数字与 0 异或（^）结果为：数字本身。

• 计算到最后只有 只出现一次的元素了。

方案一（12 ms，9696 KB）

public static int singleNumber(int[] A) {
    int length = A.length;
    if(length < 1) {
        return 0;
    } else if(length == 1) {
        return A[0];
    } else {
        Arrays.sort(A);
        int beforePointer = 0;
        int afterPointer;
        // 这个循环是不能检查 长度为 2 的数组的
        // 同时，数组的 首项和尾项 也没有判断
        for(int i = 1; i < length - 1; i++) {
            afterPointer = i + 1;
            if(A[beforePointer] != A[i] && A[afterPointer] != A[i]) {
                return A[i];
            }
            beforePointer = i;
        }
        // 没有结束，表示元素在首项或尾项
        if(A[length - 1] != A[length - 2]) {
            // 尾项
            return A[length - 1];
        } else {
            // 首项
            return A[0];
        }
    }
}

方案二（13 ms，9576 KB）

public static int singleNumber1(int[] A) {
    int sum = 0;
    for(int j : A) {
        sum ^= j;
    }
    return sum;
}