来源Leetcode第260只出现一次的数字III
给定一个整数数组 nums
,其中恰好有两个元素只出现一次,其余所有元素均出现两次。 找出只出现一次的那两个元素。
示例 :
1 | 输入: [1,2,1,3,2,5] |
Hash
建立一个值到频率的映射关系的哈希表,返回频率为 1 的数字。
1 | public int addDigits(int num) { |
位运算
来源官方题解
在做这题时没有注意到题目给出了信息其余所有元素均出现两次,这样就好说了。
首先计算 bitmask ^= x
,则 bitmask
不会保留出现两次数字的值,因为相同数字的异或值为 0
。但是 bitmask
会保留只出现一次的两个数字(x
和 y
)之间的差异。我们通过 bitmask & (-bitmask)
保留 bitmask
最右边的 1
,这个 1
要么来自 x
,要么来自 y
。当我们找到了 x
,那么 y = bitmask^x
。
另外一个解释:
1.对所有数字异或,一样的数字抵消,出现一次的两个数字异或运算后必定不为0;
2.这个数字和相反数做与运算得到一个二进制位最右边一位为1的数字;
3.mask和数组的每个数字做与运算,等于0的分为一组,等于mask的分为一组,同时也将两个不一样的数字分开;
4.完结。
1 | public int addDigits(int num) { |
1 | public int[] singleNumber(int[] nums) { |