只出现一次的数字 III

只出现一次的数字 III

  

继我们上篇的异或思想、 出现两次都异或消失

思路：

例如 示例一

异或只剩下 3 和 5

0000 0011

0000 0101

^--———^    = （result ）0000 0110 

找出result里面的第m位为1

最后两个值的第m位不一样，一个为1一个为0（id1）

按照这个思路

我们在result 中不好分离 那就在原数组中分离

---

              X1                                                                                             X2

去数组中分离出X1和X2

第M为为1的为一组       第M为为0的为一组

X1和X2第M位不同

X1  和  X2    就可以分离（id1）  他们各占一组，其他数成对出现在某一组 

// 找出result的第m位为1的位
int m = 0;
while(m<32)
{
  
if(ret & (1< 
我们用上面的例子来说明这个代价码
 
（result ）
 
0000 0110 
 
0000 0000    &    = 》 m+1 = 1    
 

 0000 0110
 
0000 0010  & =》  break
 
 
0000 0110
 
0000 0100 & = 》break
 
 
0000 0110  
 
0000 1000 & = 》m+1 = 2
 
 
0000 0110
 
0000 0100 & =》break
 
 
0000 0110
 
0000 1000  &=》 break
 
X1  和  X2    就可以分离（id1）  他们各占一组，其他数成对出现在某一组 
 
// 分离
 int x1 = 0, x2 = 0;
 for(int i = 0; i< numsSize; ++i)
{
     if(a[i] & (1< 
代码实现
 
int* singleNumber(int* nums, int numsSize, int* returnSize){
        int ret = 0;

        for(int i = 0; i < numsSize; ++i)       
      
          {
               ret ^= nums[i];
          }
        
    // 找出result的第m位为1的位
int m = 0;
       while(m<32)
{
  
       if(ret & (1<					
										


					

						
欢迎分享，转载请注明来源：内存溢出
原文地址: http://outofmemory.cn/zaji/5710465.html