136 只出现一次的数字

一、题目

给你一个 非空 整数数组 nums ，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。

你必须设计并实现线性时间复杂度的算法来解决此问题，且该算法只使用常量额外空间。

二、题解

思路： 位运算（异或）。

• 异或运算满足：任何数与 0 异或仍是它本身（a ^ 0 = a），任何数与自身异或为 0（a ^ a = 0），且满足交换律与结合律。
• 把数组中所有数字依次异或起来，出现两次的数字两两抵消为 0，最终剩下的就是那个只出现一次的数字。

class Solution {
    public int singleNumber(int[] nums) {
        int err = 0;
        // 每个数字与err异或，相同两个数异或为0，异或满足交换律，出现偶数次的数字都变成了0 (2^2 = 0)，最后剩下的为出现一次的数字
        for (int i = 0; i < nums.length; i++) {
            err ^= nums[i];
        }
        return err;
    }
}

// class Solution {
//     public int singleNumber(int[] nums) {
//         int ans = 0;
//         for(int num: nums) {
//             ans ^= num;
//         }
//         return ans;
//     }
// }

时间复杂度：$O(n)$（一次遍历数组）

空间复杂度：$O(1)$（只使用常数个额外变量）