只出现一次的数字
- 给你一个 非空 整数数组 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)，只使用了常量额外空间。
