【技巧】Leetcode 136. 只出现一次的数字【中等】

只出现一次的数字

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

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

示例1：

输入：nums = [2,2,1]
输出：1

解题思路

可以使用位运算中的异或（XOR）操作。

• 异或运算有以下性质：

• 1、任何数和0异或，结果仍为原来的数：a ⊕ 0 = a

• 2、任何数和自己异或，结果为0：a ⊕ a = 0

• 3、异或运算满足交换律和结合律：a ⊕ b ⊕ a = (a ⊕ a) ⊕ b = 0 ⊕ b = b

对应这个问题

• 可以遍历整个数组，对数组中的所有元素进行异或操作。
• 由于数组中除了一个元素只出现一次，其余每个元素都出现两次，
• 因此相同的元素进行异或运算后结果为 0。而任何数和 0 进行异或运算的结果仍然是原来的数。

Java实现

public class SingleNumber {
    public static int singleNumber(int[] nums) {
        int result = 0;
        for (int num : nums) {
            result ^= num;
        }
        return result;
    }

    public static void main(String[] args) {

        int[] nums = {4, 2, 2, 1, 1,4,125};
        System.out.println(singleNumber(nums));
    }
}

时间空间复杂度

• 时间复杂度：O(n)，其中 n 是数组 nums 的长度，因为我们需要遍历所有元素。

• 空间复杂度：O(1)，只使用了常量额外空间。