LeetCode：只出现一次的数字

一、题目描述

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

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

二、分析

如果不考虑时间复杂度和空间复杂度的限制，这道题有很多种解法（我个人想到使用的是HashMap存储）

对于这道题，可使用异或运算 ⊕。异或运算有以下三个性质。

• 任何数和 0 做异或运算，结果仍然是原来的数，即 a⊕0=a。
• 任何数和其自身做异或运算，结果是 0，即 a⊕a=0。
• 异或运算满足交换律和结合律，即 a⊕b⊕a = b⊕a⊕a = b⊕(a⊕a) = b⊕0 = b。

三、上代码

方法一：（使用HashMap存储key为元素x，value为次数）

public int singleNumber(int[] nums) {Map<Integer, Integer> map = new HashMap<>();for (int x : nums) {if (map.containsKey(x)) {int value  = map.get(x) + 1;map.put(x, value);} else {map.put(x, 1);}}for (int x : map.keySet()) {if (map.get(x) == 1) {return x;}}return -1;}

方法二：使用异或

• a ^ a = 0;
• 0 ^ a = a;

public int deal(int[] nums) {int single = 0;for (int x : nums) {single ^= x;}return single;}