137. 只出現一次的數字 II（點擊查看題目）
題目描述
給定一個 非空 整數數組，除了某個元素只出現一次以外，其餘每個元素均出現了三次。找出那個只出現了一次的元素。
說明：
你的算法應該具有線性時間複雜度。你可以不使用額外空間來實現嗎？
示例 1:
<code>輸入: [2,2,3,2]
輸出: 3/<code>
示例 2:
<code>輸入: [0,1,0,1,0,1,99]
輸出: 99/<code>
解決方案
綜述
該問題看起來很簡單，使用 Set 或 HashMap 可以在 O(N) 的時間和 O(N) 的空間內解決。
真正的挑戰在於 Google 面試官要求使用常數空間解決該問題（最近 6 個月該問題在 Google 上非常流行），測試應聘者是否熟練位操作。
方法一：HashSet
將輸入數組存儲到 HashSet，然後使用 HashSet 中數字和的三倍與數組之和比較。
3 × (a + b + c) - ( a + a + a + b + b + b + c) = 2c
Python 實現（可在電腦端查看代碼）
<code>class Solution:
def singleNumber(self, nums):
return (3 * sum(set(nums)) - sum(nums)) // 2/<code>
Java 實現（可在電腦端查看代碼）
<code>class Solution {
public int singleNumber(int[] nums) {
Set<long> set = new HashSet<>();
long sumSet = 0, sumArray = 0;
for(int n : nums) {
sumArray += n;
set.add((long)n);
}
for(Long s : set) sumSet += s;
return (int)((3 * sumSet - sumArray) / 2);
}
}/<long>/<code>複雜度分析
- 時間複雜度：O(N)，遍歷輸入數組。
- 空間複雜度：O(N)，存儲 N / 3 個元素的集合。
方法二：HashMap
遍歷輸入數組，統計每個數字出現的次數，最後返回出現次數為 1 的數字。
Python 實現（可在電腦端查看代碼）
<code>from collections import Counter
class Solution:
def singleNumber(self, nums):
hashmap = Counter(nums)
for k in hashmap.keys():
if hashmap[k] == 1:
return k/<code>
Java 實現（可在電腦端查看代碼）
<code>class Solution {
public int singleNumber(int[] nums) {
HashMap<integer> hashmap = new HashMap<>();
for (int num : nums)
hashmap.put(num, hashmap.getOrDefault(num, 0) + 1);
for (int k : hashmap.keySet())
if (hashmap.get(k) == 1) return k;
return -1;
}
}/<integer>/<code>複雜度分析
- 時間複雜度：O(N)，遍歷輸入數組。
- 空間複雜度：O(N)，存儲 N / 3 個元素的 Set。
方法三：位運算符：NOT，AND 和 XOR
思路
使用 位運算符 可以實現 O(1) 的空間複雜度。
XOR
該運算符用於檢測出現奇數次的位：1、3、5 等。
0 與任何數 XOR 結果為該數。
兩個相同的數 XOR 結果為 0。
以此類推，只有某個位置的數字出現奇數次時，該位的掩碼才不為 0。
因此，可以檢測出出現一次的位和出現三次的位，但是要注意區分這兩種情況。
AND 和 NOT
為了區分出現一次的數字和出現三次的數字，使用兩個位掩碼：seen_once 和 seen_twice。
思路是：
位掩碼 seen_once 僅保留出現一次的數字，不保留出現三次的數字。
Python 實現（可在電腦端查看代碼）
<code>class Solution:
def singleNumber(self, nums: List[int]) -> int:
seen_once = seen_twice = 0
for num in nums:
# first appearance:
# add num to seen_once
# don't add to seen_twice because of presence in seen_once
# second appearance:
# remove num from seen_once
# add num to seen_twice
# third appearance:
# don't add to seen_once because of presence in seen_twice
# remove num from seen_twice
seen_once = ~seen_twice & (seen_once ^ num)
seen_twice = ~seen_once & (seen_twice ^ num)
return seen_once/<code>
Java 實現（可在電腦端查看代碼）
<code>class Solution {
public int singleNumber(int[] nums) {
int seenOnce = 0, seenTwice = 0;
for (int num : nums) {
// first appearence:
// add num to seen_once
// don't add to seen_twice because of presence in seen_once
// second appearance:
// remove num from seen_once
// add num to seen_twice
// third appearance:
// don't add to seen_once because of presence in seen_twice
// remove num from seen_twice
seenOnce = ~seenTwice & (seenOnce ^ num);
seenTwice = ~seenOnce & (seenTwice ^ num);
}
return seenOnce;
}
}/<code>複雜度分析
- 時間複雜度：O(N)，遍歷輸入數組。
- 空間複雜度：O(1)，不使用額外空間。
閱讀更多 力扣LeetCode 的文章
