給定一個整數陣列nums，其中恰好有兩個元素只出現一次，其余元素均出現兩次，找出只出現一次的那兩個元素，你可以按任意順序回傳答案，
示例：
?輸入：nums = [1, 2, 1, 3, 2, 5]
?輸出：[3, 5]
思路：
陣列nums當中存在兩個只出現一次的元素，我們不能直接通過對陣列元素進行異或得到只出現一次的元素，但如果我們可以將陣列當中的元素分為兩小組元素，而這兩個只出現了一次的元素分別位于這兩個不同的小組，那么我們就可以通過對兩個小組進行組內異或得到兩個異或后的結果，這兩個結果就是陣列nums當中只出現一次的兩個元素，
第一步：將陣列nums當中的所有元素進行異或操作，得到異或后的結果ret， 因為陣列當中只有兩個元素只出現一次，其余元素均出現兩次，而兩個相同的元素進行異或后就沒有了，所以最終異或的結果ret便是這兩個只出現了一次的兩個元素相異或的結果，
第二步：在異或后所得到的結果ret的32個bit位當中，任意找到一個不為0的bit位div， 因為最終異或的結果ret等價于那兩個只出現了一次的兩個元素相異或的結果，而兩個不相等的數相異或后一定不為0，所以一定能在ret的32個bit位中找到至少一個不為0的bit位，
第三步：根據div將陣列當中的元素分為兩組，元素div位置的bit位為0的為第一組，元素div位置的bit位為1的為第二組， 因為那兩個只出現了一次的元素的div位置的bit位是一定不同的，所以經過該操作后兩個只出現一次的元素被分到了兩個不同的組，
第四步：分別對第一組和第二組的元素進行組內異或，最終得到兩個異或后的結果a和b，a和b便是nums陣列當中只出現一次的兩個元素，
代碼如下：
class Solution {
public:
vector<int> singleNumber(vector<int>& nums) {
int ret = 0; //陣列中所有元素進行異或后的結果
//通過范圍for遍歷陣列，對陣列中的所有元素進行異或
for (auto e : nums)
{
ret ^= e;
}
int div = 1; //標記ret的32個bit位中某個不為0的bit位
//從右向左尋找ret的32個bit位中第一個不為0的bit位
while ((ret&div) == 0)
{
div <<= 1; //從右向左尋找bit位
}
int a = 0, b = 0; //分別存盤兩個只出現一次的元素
for (auto e : nums)
{
if (e&div) //元素div位置的bit位為1的為一組進行異或
a ^= e;
else //元素div位置的bit位為0的為一組進行異或
b ^= e;
}
//將兩個只出現一次的元素放到容器v當中
vector<int> v;
v.push_back(a);
v.push_back(b);
return v; //回傳容器v
}
};
轉載請註明出處，本文鏈接：https://www.uj5u.com/ruanti/297886.html
標籤：其他