給定一個整數數組 nums，其中恰好有兩個元素只出現一次，其余所有元素均出現兩次。 找出只出現一次的那兩個元素。
示例 :
輸入: [1,2,1,3,2,5]
輸出: [3,5]
注意：
結果輸出的順序并不重要，對于上面的例子， [5, 3] 也是正確答案。
你的算法應該具有線性時間復雜度。你能否僅使用常數空間復雜度來實現？
來源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/single-number-iii
著作權歸領扣網絡所有。商業轉載請聯系官方授權，非商業轉載請注明出處。

這一個問題與我們上一次完成的leetcode-136很像，它將只出現一次的元素換成了兩個
leetcode-136 解法：https://blog.csdn.net/qq_35423154/article/details/101792655
對于這個問題，我們不能再像上次一樣直接遍歷異或，因為有兩個只出現了一次的元素，我們需要找一個方法來把它們兩個分開。
設
于是我們能想到，首先我們先按照上次的寫法將數組遍歷一遍，得到了它們兩個的異或值

for(i=0; i<nums.size(); i++){flag ^= nums[i];}

我們就得到了它們二進制位的關系，然后我們需要得到它們在某一位上的不同，借助那個不同將數組分為兩個，例如：
5：0101
13：1101
5^13:1000
我們可以借助這個1，將數組中該項為1的數分成一份，該項為0的數分為一份，這樣我們遍歷異或就可以直接得到答案。
但如果多個位上存在1時，我們只需要取一個
所以：

flag &= -flag;

如:
00001101
取負數得:
11110011
取與得:
00000001
即可得到單獨二進制位上的1

下面再繼續用上次的解法

{if((nums[i] & flag) ==0)x ^= nums[i];elsey ^= nums[i];}

即可分別得到x,y的值
完整代碼如下

class Solution { public:vector<int> singleNumber(vector<int>& nums) {int flag=0,i,x=0,y=0;for(i=0; i<nums.size(); i++){flag ^= nums[i];}flag &= -flag;for(i=0; i<nums.size(); i++){if((nums[i] & flag) ==0)x ^= nums[i];elsey ^= nums[i];}return {x,y};}};

總結

以上是生活随笔為你收集整理的leetcode-260.只出现一次的数字 III 解法的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。