137. Single Number II
給定一個整數數組 nums，其中每個元素都出現三次，只有一個元素只出現一次。找出這個單獨的元素並返回它。
你必須實現一個線性運行時間複雜度的解決方案，並且只使用恆定的額外空間。
Python
from typing import List
class Solution:
def singleNumber(self, nums: List[int]) -> int:
ones, twos = 0, 0
for num in nums:
# `ones` will keep track of the bits that appear exactly once
ones = (ones ^ num) & ~twos
# `twos` will keep track of the bits that appear exactly twice
twos = (twos ^ num) & ~ones
return ones
18.6MB, 54ms
C++
#include <vector>
using namespace std;
class Solution {
public:
int singleNumber(vector<int>& nums) {
int ones = 0, twos = 0;
for (int num : nums) {
// `ones` will keep track of the bits that appear exactly once
ones = (ones ^ num) & ~twos;
// `twos` will keep track of the bits that appear exactly twice
twos = (twos ^ num) & ~ones;
}
return ones;
}
};
11.88MB, 4ms
Javascript
/**
* @param {number[]} nums
* @return {number}
*/
var singleNumber = function(nums) {
let ones = 0, twos = 0;
for (let num of nums) {
// `ones` will keep track of the bits that appear exactly once
ones = (ones ^ num) & ~twos;
// `twos` will keep track of the bits that appear exactly twice
twos = (twos ^ num) & ~ones;
}
return ones;
};
51.21MB, 54ms
