LeetCode 题解 | 260. 只出现一次的数字 III 力扣260.只出现一次的数字III（

文章插图
力扣 260. 只出现一次的数字 III（点击查看题目）
题目描述
给定一个整数数组 nums ，其中恰好有两个元素只出现一次，其余所有元素均出现两次。找出只出现一次的那两个元素。
示例：
输入: [1,2,1,3,2,5]输出: [3,5]注意：

结果输出的顺序并不重要，对于上面的例子，[5, 3] 也是正确答案。
你的算法应该具有线性时间复杂度。你能否仅使用常数空间复杂度来实现？

解决方案
概述使用哈希表可以在 O(N) 的时间复杂度和 O(N) 的空间复杂度中解决该问题。
这个问题在常数的空间复杂度中解决有点困难，但可以借助两个位掩码来实现。

文章插图
方法一：哈希表
建立一个值到频率的映射关系的哈希表，返回频率为 1 的数字。
算法：
Python 实现（可在电脑端查看代码）

from collections import Counterclass Solution:def singleNumber(self, nums: int) -> List[int]:hashmap = Counter(nums)return [x for x in hashmap if hashmap[x] == 1]

Java 实现（可在电脑端查看代码）

class Solution {public int[] singleNumber(int[] nums) {Map hashmap = new HashMap();for (int n : nums)hashmap.put(n, hashmap.getOrDefault(n, 0) + 1);int[] output = new int[2];int idx = 0;for (Map.Entry item : hashmap.entrySet())if (item.getValue() == 1) output[idx++] = item.getKey();return output;}}

复杂度分析
时间复杂度：O(N)
空间复杂度：O(N)，哈希表所使用的空间。
方法二：两个掩码本文将使用两个按位技巧：

使用异或运算可以帮助我们消除出现两次的数字；我们计算 bitmask ^= x ，则 bitmask 留下的就是出现奇数次的位。

文章插图

xfor (int num : nums) bitmask ^= num;// rightmost 1-bit diff between x and yint diff = bitmaskint x = 0;// bitmask which will contain only xfor (int num : nums) if ((numreturn new int[]{x, bitmask^x};}}复杂度分析
时间复杂度：O(N) 的时间遍历输入数组。
空间复杂度：O(1)。
本文作者：力扣
【LeetCode 题解 | 260. 只出现一次的数字 III】声明：本文归“力扣”版权所有，如需转载请联系。