给你一个整数数组 nums，其中恰好有两个元素只出现一次，其余所有元素均出现两次。 找出只出现一次的那两个元素。你可以按 任意顺序 返回答案。
你必须设计并实现线性时间复杂度的算法且仅使用常量额外空间来解决此问题。
示例 1：
**输入：** nums = [1,2,1,3,2,5]
**输出：** [3,5]
**解释：** [5, 3] 也是有效的答案。
示例 2：
**输入：** nums = [-1,0]
**输出：** [-1,0]
示例 3：
**输入：** nums = [0,1]
**输出：** [1,0]
提示：
2 <= nums.length <= 3 * 104-231 <= nums[i] <= 231 - 1除两个只出现一次的整数外，nums 中的其他数字都出现两次
📺 视频题解
📖 文字题解 方法一：哈希表 思路与算法
我们可以使用一个哈希映射统计数组中每一个元素出现的次数。
在统计完成后，我们对哈希映射进行遍历，将所有只出现了一次的数放入答案中。
代码
[sol1-C++] 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 class Solution {public : vector<int > singleNumber (vector<int >& nums) { unordered_map<int , int > freq; for (int num: nums) { ++freq[num]; } vector<int > ans; for (const auto & [num, occ]: freq) { if (occ == 1 ) { ans.push_back (num); } } return ans; } };
[sol1-Java] 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 class Solution { public int [] singleNumber(int [] nums) { Map<Integer, Integer> freq = new HashMap <Integer, Integer>(); for (int num : nums) { freq.put(num, freq.getOrDefault(num, 0 ) + 1 ); } int [] ans = new int [2 ]; int index = 0 ; for (Map.Entry<Integer, Integer> entry : freq.entrySet()) { if (entry.getValue() == 1 ) { ans[index++] = entry.getKey(); } } return ans; } }
[sol1-C#] 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 public class Solution { public int [] SingleNumber (int [] nums Dictionary<int , int > freq = new Dictionary<int , int >(); foreach (int num in nums) { if (freq.ContainsKey(num)) { ++freq[num]; } else { freq.Add(num, 1 ); } } int [] ans = new int [2 ]; int index = 0 ; foreach (KeyValuePair<int , int > pair in freq) { if (pair.Value == 1 ) { ans[index++] = pair.Key; } } return ans; } }
[sol1-Python3] 1 2 3 4 class Solution : def singleNumber (self, nums: List [int ] ) -> List [int ]: freq = Counter(nums) return [num for num, occ in freq.items() if occ == 1 ]
[sol1-JavaScript] 1 2 3 4 5 6 7 8 9 10 11 12 13 var singleNumber = function (nums ) { const freq = new Map (); for (const num of nums) { freq.set (num, (freq.get (num) || 0 ) + 1 ); } const ans = []; for (const [num, occ] of freq.entries ()) { if (occ === 1 ) { ans.push (num); } } return ans; };
[sol1-TypeScript] 1 2 3 4 5 6 7 8 9 10 11 12 13 function singleNumber (nums: number [] ): number [] { const freq = new Map (); for (const num of nums) { freq.set (num, (freq.get (num) || 0 ) + 1 ); } const ans : number [] = []; for (const [num, occ] of freq.entries ()) { if (occ === 1 ) { ans.push (num); } } return ans; };
[sol1-Golang] 1 2 3 4 5 6 7 8 9 10 11 12 func singleNumber (nums []int ) int ) { freq := map [int ]int {} for _, num := range nums { freq[num]++ } for num, occ := range freq { if occ == 1 { ans = append (ans, num) } } return }
复杂度分析
方法二：位运算 思路与算法
在理解如何使用位运算解决本题前，读者需要首先掌握「136. 只出现一次的数字」 中的位运算做法。
假设数组 $\textit{nums}$ 中只出现一次的元素分别是 $x_1$ 和 $x_2$。如果把 $\textit{nums}$ 中的所有元素全部异或起来，得到结果 $x$，那么一定有：
$$
其中 $\oplus$ 表示异或运算。这是因为 $\textit{nums}$ 中出现两次的元素都会因为异或运算的性质 $a \oplus b \oplus b = a$ 抵消掉，那么最终的结果就只剩下 $x_1$ 和 $x_2$ 的异或和。
$x$ 显然不会等于 $0$，因为如果 $x=0$，那么说明 $x_1 = x_2$，这样 $x_1$ 和 $x_2$ 就不是只出现一次的数字了。因此，我们可以使用位运算 $\texttt{x & -x}$ 取出 $x$ 的二进制表示中最低位那个 $1$，设其为第 $l$ 位，那么 $x_1$ 和 $x_2$ 中的某一个数的二进制表示的第 $l$ 位为 $0$，另一个数的二进制表示的第 $l$ 位为 $1$。在这种情况下，$x_1 \oplus x_2$ 的二进制表示的第 $l$ 位才能为 $1$。
这样一来，我们就可以把 $\textit{nums}$ 中的所有元素分成两类，其中一类包含所有二进制表示的第 $l$ 位为 $0$ 的数，另一类包含所有二进制表示的第 $l$ 位为 $1$ 的数。可以发现：
因此，如果我们将每一类的元素全部异或起来，那么其中一类会得到 $x_1$，另一类会得到 $x_2$。这样我们就找出了这两个只出现一次的元素。
代码
[sol2-C++] 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 class Solution {public : vector<int > singleNumber (vector<int >& nums) { int xorsum = 0 ; for (int num: nums) { xorsum ^= num; } int lsb = (xorsum == INT_MIN ? xorsum : xorsum & (-xorsum)); int type1 = 0 , type2 = 0 ; for (int num: nums) { if (num & lsb) { type1 ^= num; } else { type2 ^= num; } } return {type1, type2}; } };
[sol2-Java] 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 class Solution { public int [] singleNumber(int [] nums) { int xorsum = 0 ; for (int num : nums) { xorsum ^= num; } int lsb = (xorsum == Integer.MIN_VALUE ? xorsum : xorsum & (-xorsum)); int type1 = 0 , type2 = 0 ; for (int num : nums) { if ((num & lsb) != 0 ) { type1 ^= num; } else { type2 ^= num; } } return new int []{type1, type2}; } }
[sol2-C#] 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 public class Solution { public int [] SingleNumber (int [] nums int xorsum = 0 ; foreach (int num in nums) { xorsum ^= num; } int lsb = (xorsum == int .MinValue ? xorsum : xorsum & (-xorsum)); int type1 = 0 , type2 = 0 ; foreach (int num in nums) { if ((num & lsb) != 0 ) { type1 ^= num; } else { type2 ^= num; } } return new int []{type1, type2}; } }
[sol2-Python3] 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 class Solution : def singleNumber (self, nums: List [int ] ) -> List [int ]: xorsum = 0 for num in nums: xorsum ^= num lsb = xorsum & (-xorsum) type1 = type2 = 0 for num in nums: if num & lsb: type1 ^= num else : type2 ^= num return [type1, type2]
[sol2-JavaScript] 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 var singleNumber = function (nums ) { let xorsum = 0 ; for (const num of nums) { xorsum ^= num; } let type1 = 0 , type2 = 0 ; const lsb = xorsum & (-xorsum); for (const num of nums) { if (num & lsb) { type1 ^= num; } else { type2 ^= num; } } return [type1, type2]; };
[sol2-Golang] 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 func singleNumber (nums []int ) int { xorSum := 0 for _, num := range nums { xorSum ^= num } lsb := xorSum & -xorSum type1, type2 := 0 , 0 for _, num := range nums { if num&lsb > 0 { type1 ^= num } else { type2 ^= num } } return []int {type1, type2} }
[sol2-C] 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 int * singleNumber (int * nums, int numsSize, int * returnSize) { int xorsum = 0 ; for (int i = 0 ; i < numsSize; i++) { xorsum ^= nums[i]; } int lsb = (xorsum == INT_MIN ? xorsum : xorsum & (-xorsum)); int type1 = 0 , type2 = 0 ; for (int i = 0 ; i < numsSize; i++) { int num = nums[i]; if (num & lsb) { type1 ^= num; } else { type2 ^= num; } } int *ans = (int *)malloc (sizeof (int ) * 2 ); ans[0 ] = type1; ans[1 ] = type2; *returnSize = 2 ; return ans; }
复杂度分析
