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

力扣 260. 只出现一次的数字 III（点击查看题目）

题目描述

给定一个整数数组 nums，其中恰好有两个元素只出现一次，其余所有元素均出现两次。找出只出现一次的那两个元素。

示例：

<code>输入: 
[1,2,1,3,2,5]
输出: 
[3,5]
/<code>

注意：

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

解决方案

概述

使用哈希表可以在 O(N) 的时间复杂度和 O(N) 的空间复杂度中解决该问题。

这个问题在常数的空间复杂度中解决有点困难，但可以借助两个位掩码来实现。

方法一：哈希表

建立一个值到频率的映射关系的哈希表，返回频率为 1 的数字。

算法：

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

<code>
from
 collections 
import
 Counter
class
 
Solution
:

    
def
 
singleNumber
(self, nums: int)
 -> List[int]:

        hashmap = Counter(nums)
        
return
 [x 
for
 x 
in
 hashmap 
if
 hashmap[x] == 
1
]/<code>

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

<code>
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;
  }
}/<code>

复杂度分析

时间复杂度：O(N)

空间复杂度：O(N) ，哈希表所使用的空间。

方法二：两个掩码

本文将使用两个按位技巧：

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

• x & (-x) 是保留位中最右边 1 ，且将其余的 1 设位 0 的方法。

算法：

首先计算 bitmask ^= x，则 bitmask 不会保留出现两次数字的值，因为相同数字的异或值为 0。

但是 bitmask 会保留只出现一次的两个数字（x 和 y）之间的差异。

我们可以直接从 bitmask 中提取 x 和 y 吗？不能，但是我们可以用 bitmask作为标记来分离 x 和 y。

我们通过 bitmask & (-bitmask) 保留 bitmask 最右边的 1，这个 1 要么来自 x，要么来自 y。

当我们找到了 x，那么 y = bitmask^x。

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

<code>
class
 
Solution:
    
def
 
singleNumber(self, nums: int) -> List[int]:
 
        
bitmask
 = 
0
        
for
 
num in nums:
            
bitmask
 
^= num
 
        
diff
 = 
bitmask & (-bitmask)
        
        
x
 = 
0
        
for
 
num in nums:
 
            
if
 
num & diff:
                
x
 
^= num
        
        
return 
 
[x, bitmask^x]
/<code>

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

<code>
class
 
Solution
 {
  
public
 
int
[] 
singleNumber
(
int
[] nums
)
 {
     
    
int
 bitmask = 
0
;
    
for
 (
int
 num : nums) bitmask ^= num;

     
    
int
 diff = bitmask & (-bitmask);

    
int
 x = 
0
;
     
    
for
 (
int
 num : nums) 
if
 ((num & diff) != 
0
) x ^= num;

    
return
 
new
  
int
[]{x, bitmask^x};
  }
}/<code>

复杂度分析

时间复杂度：O(N) 的时间遍历输入数组。

空间复杂度：O(1) 。

本文作者：力扣

声明：本文归“力扣”版权所有，如需转载请联系。