Re: [閒聊] 每日leetcode已回收
260. Single Number III
有一個整數array，在這個array中有兩個數字只出現一次
其他數字都出現兩次
請找出這兩個數字
思路:
把nums所有元素都XOR會得到一個值
這個值就是所求的兩個數(A、B)XOR的結果
且A、B不相等所以這個值不會是0
假設這個值第i個bit=1-->A、B在第i個bit的值不同
就依照第i個bit的值，把nums的元素分成兩堆
最後把這兩堆分別XOR就可以得到A、B了
C code:
/**
* Note: The returned array must be malloced, assume caller calls free().
*/
int* singleNumber(int* nums, int numsSize, int* returnSize) {
*returnSize=2;
if (numsSize==2){
return nums;
}
int sum=0,*res=(int*)calloc(2,sizeof(int)),idx=0;
for (int i=0;i<numsSize;i++){
sum^=nums[i];
}
while(1){
if (((sum>>idx)&1)==1){
break;
}
idx++;
}
for (int i=0;i<numsSize;i++){
if (((nums[i]>>idx)&1)==1){
res[0]^=nums[i];
}else{
res[1]^=nums[i];
}
}
return res;
}
--
https://i.imgur.com/r9FBAGO.gif
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 111.71.215.194 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1717159275.A.F7B.html
推
05/31 20:42,
1年前
, 1F
05/31 20:42, 1F
推
05/31 20:43,
1年前
, 2F
05/31 20:43, 2F
→
05/31 20:43,
1年前
, 3F
05/31 20:43, 3F
推
05/31 20:44,
1年前
, 4F
05/31 20:44, 4F
推
05/31 20:44,
1年前
, 5F
05/31 20:44, 5F
推
05/31 20:44,
1年前
, 6F
05/31 20:44, 6F
推
05/31 20:47,
1年前
, 7F
05/31 20:47, 7F
推
05/31 20:55,
1年前
, 8F
05/31 20:55, 8F
→
05/31 21:16,
1年前
, 9F
05/31 21:16, 9F
→
05/31 21:44,
1年前
, 10F
05/31 21:44, 10F
討論串 (同標題文章)
完整討論串 (本文為第 303 之 1554 篇)：