雖然不知道為什麼負數最小值無法被qsort 處理（？）
（可能是最後的相減會爆掉？！）
雖然先sorting 好像也不符合題目要求（？！）
但總之先來一個不會過的版本 XD
int comp(const void *a , const void *b){
return ( *(int*) a- *(int*)b);
}
int singleNumber(int* nums, int numsSize){
qsort((void*)nums , numsSize,sizeof(int), comp);
if (numsSize==1)
return nums[0];
int i;
for (int i=0;i<numsSize; i+=3)
{
if ((i==numsSize-1) || (nums[i]!=nums[i+1]))
return nums[i];
if (nums[i]==nums[i+1])
continue;
}
return nums[i];
}
然後讓我們來看看這題的奧義～bit manipulation！！！
天啊這也太難了Orz
而且如果用十進位的想法去想的話，根本就覺得"為什麼可以這樣做！" XD
為什麼數字不會被蓋掉呢～真的好玄喔 XD
先把code貼一下:
int singleNumber(int* nums, int numsSize){
int one=0;
int two=0;
for (int i=0; i<numsSize; i++)
{
one = (one ^ nums[i]) & ~two;
two = (two ^ nums[i]) & ~one;
}
return one;
}
然後解答區的英文寫的落落長，最後我決定搜尋中文的說明XD
看了以後有比較懂一點了 ！！！
Link 在此: https://ithelp.ithome.com.tw/articles/10242654
大意就是說，
（1）數字進來, 我們先把它放進one。並且如果這個數字已經在two了，就把它從one拿掉。（後面的 & ~two 就是看它在不在two，有的話從one拿掉的意思。
（2）接著我們把同一個數字存進去two裡面，如果它在one了，就從two拿掉。也就是不存進去two 的意思！ 因為所有數字都會先經過one，所以只來一次的數字會先待在one, 不存進去two，或者說存不進去two。
（3）當同一個數字來了第二次的時候，會發生的事:
a.它想存進one的時候，因為one已經有它了，因此這個數字會被XOR消滅。 &~two的部分因為two裡也沒有這個值，所以沒影響。
b.接著two做了XOR的時候，原本沒有它，因此可以進來；後面的 &~one 因為上面a的作為，這個數字已經不在one裡了，所以 [如果它在one了，就從two拿掉。] 這步不會做，因此它可以被存在 two 。
（4）當這個數字來第三次的時候，它想加進one，但因為two裡已經有這個值了，所以 & ~two產生作用，這個數字不會進one.
最後最後one剩下的就是那個只來一次的值了。
用一個簡單的例子應該可以看懂這一切 XD
Input
nums =
[10,4,10,10,4,4,99]
Stdout
0 one[0] two [0]
1 one[10] two [0]
2 one[14] two [0]
3 one[4] two [10]
4 one[4] two [0]
5 one[0] two [4]
6 one[0] two [0]
沒有留言:
張貼留言