56-I. 数组中数字出现的次数
1. 描述
一个整型数组 nums 里除两个数字之外，其他数字都出现了两次。请写程序找出这两个只出现一次的数字。要求时间复杂度是O(n)，空间复杂度是O(1)。
2. 例子
示例 1:
输入：nums = [4,1,4,6]
输出：[1,6] 或 [6,1]
示例 2:
输入：nums = [1,2,10,4,1,4,3,3]
输出：[2,10] 或 [10,2]
3. 限制
- 2 <= nums.length <= 10000
4. 题解
n = m_nums.size()
时间复杂度: O(n)
空间复杂度: O(1)
class Solution
{
public:
// vector<int> singleNumbers(vector<int>& nums)
vector<int> singleNumbers(vector<int> &m_nums)
{
int twoUniqueNumbersXOR = 0;
for(int i = 0; i < m_nums.size(); i++)
twoUniqueNumbersXOR ^= m_nums[i];
int digitOne = 0;
for(int i = 0; i < 32; i++)
{
if((1 << i) & twoUniqueNumbersXOR)
{
digitOne = (1 << i);
break;
}
}
vector<int> uniqueTwoNumbers{0, 0};
for(int i = 0; i < m_nums.size(); i++)
{
if(m_nums[i] & digitOne) uniqueTwoNumbers[0] ^= m_nums[i];
else uniqueTwoNumbers[1] ^= m_nums[i];
}
return uniqueTwoNumbers;
}
};