問題描述：
一個整型陣列 nums 里除兩個數字之外，其他數字都出現了兩次，請寫程式找出這兩個只出現一次的數字，要求時間復雜度是O(n)，空間復雜度是O(1)，
示例 1：
輸入：nums = [4,1,4,6]
輸出：[1,6] 或 [6,1]
示例 2：
輸入：nums = [1,2,10,4,1,4,3,3]
輸出：[2,10] 或 [10,2]
問題分析：
在人群中找出那兩條單身狗？
1.首先如果是，其他數字都出現了兩次，只有一個數字出現一次，怎么找到這個數字？
即全員異或操作，成對出現的數字的所有位會兩兩抵消為 0，最終得到的結果就是那個出現了一次的數字， 3⊕3⊕5⊕5⊕6，最終結果是6
異或：
2.回到原問題，找出這兩個只出現一次的數字，例如為335567
最終要求出6，7
a.先對所有數字進行一次異或，得到兩個出現一次的數字的異或值result，result!=0，
根據得到的結果result，根據result找到67相互嫌棄的點在哪，
即在result中找到任意為 1的位，
6：1 1 0
7：1 1 1
b.根據這個互相嫌棄的點，分成兩組，對所有的數字進行遍歷，
本著兩家人不進一家門的原則，6，7就不會被分到一個組了，
成對出現的數字，會被它相同的數字領走，
例如第一個3先進了6這個組，當遍歷第二個3時，這個第二個三就把第一個三領走了，他們最侄訓相遇，即他們抵消掉了，
就這樣在每個組內進行異或操作，最終剩下6，7分在不同組里，
c.總結：全程只有那倆不相同的數字互相嫌棄，最終他們會被分到不同的組，
代碼：
public int[] singleNumbers(int[] nums) {
int result=nums[0];
for(int i=1;i<nums.length;i++)
result^=nums[i];//異或結果
int diff=1;
while((diff&result)==0){
diff<<=1;//找到為1的位
}
int a=0,b=0;
for(int i=0;i<nums.length;i++)
{
if((diff&nums[i])==0)
a^=nums[i];//a組
else
b^=nums[i];//b組
}
return new int[]{a,b};
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/275865.html
標籤：其他
上一篇：藍橋杯第十二屆模擬題