※ 引述《ray90514 ()》之銘言：
: 260. Single Number III
: 很直覺的全部做xor答案以外會被消掉
: 接下來就是想辦法找出這兩數 這部分就有點卡住
: xor出來該位值1代表兩數該位相異
: 依照該位將數列分成兩部分
: 因為同樣的數也會被分在一起 所以xor後就是答案
: 別問我怎麼想到的==
: 還沒看討論不知道有沒有更好的做法
: class Solution {
: public:
: vector<int> singleNumber(vector<int>& nums) {
: int sum = 0;
: for(int n : nums){
: sum ^= n;
: }
: int base = 1;
: while(!(sum & base))
: base <<= 1;
: int even = 0, odd = 0;
: for(int n : nums){
: if(n & base)
: even ^= n;
: else
: odd ^= n;
: }
: return {odd, even};
: }
: };
一樣
不過base那邊可以利用正負數在bit的表示方法
C# code
public class Solution {
public int[] SingleNumber(int[] nums) {
int xor = 0;
foreach (var num in nums) xor ^= num;
int diff = xor & (-xor);
int num1=0, num2=0;
foreach (var num in nums)
{
if ((num&diff) == 0) num1 ^= num;
else num2 ^= num;
}
return new int[] {num1, num2};
}
}