題目
一個整型數組 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]
限制：
2 <= nums <= 10000
代碼
class Solution {
public int[] singleNumbers(int[] nums) {
int x = 0;
for(int n:nums)
x^=n;
//此時x相當于兩個只出現一次的數字的異或
int y = 1;
while((y&x)==0){
y<<=1;
}
//y為x的第一個為1的位
int n1=0,n2=0;
for(int n:nums){ //將nums數組分為兩部分 可以分開其中只出現一次的兩個數
if((n&y)==0)
n1^=n;
else
n2^=n;
}
int[] ans = {n1,n2};
return ans;
}
}
時間復雜度O(n) 空間復雜度O(1)
浙公網安備 33010602011771號
浙ICP備2021040463號-3
