136_只出现一次的数字

风扫地

1. /*
   
2. 给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。
   
3. 
   
4. 说明：
   
5. 
   
6. 你的算法应该具有线性时间复杂度。 你可以不使用额外空间来实现吗？
   
7. 
   
8. 示例 1:
   
9. 
   
10. 输入: [2,2,1]
    
11. 输出: 1
    
12. 示例 2:
    
13. 输入: [4,1,2,1,2]
    
14. 输出: 4
    
15. */

复制代码

1. int singleNumber(int* nums, int numsSize){
   
2.    
   
3.     int ret_val = 0;
   
4.     int i = 0;
   
5.    
   
6.     for(i = 0; i <numsSize;i++)
   
7.     {
   
8.         ret_val ^= nums[i];
   
9.     }
   
10.     return ret_val;
    
11. 
    
12. }
    

复制代码

1. /*
   
2. 最近提交结果：
   
3. 通过
   
4. 显示详情
   
5. 执行用时 :12 ms, 在所有C提交中击败了99.46% 的用户
   
6. 内存消耗 :7.9 MB, 在所有C提交中击败了40.52%的用户
   
7. 
   
8. 
   
9. 16 / 16 个通过测试用例 状态：通过
   
10. 执行用时：12 ms
    
11. 提交时间：0 分钟之前
    
12. 
    
13. */

复制代码

风扫地

利用异或特性～

Seawolf

看不懂你说的异或怎么在你的code里体现，能解释一下吗，我用python写了一个，runtime：60ms

1. class Solution:
   
2.     def singleNumber(self, L):
   
3.         head = self.get_head(L)
   
4.         tail = self.get_tail(L)
   
5.         if head in tail:
   
6.             L1 = self.delete(head,tail)
   
7.             self.singleNumber(L1)
   
8.         else:
   
9.             print(head)
   
10.         
    
11.     def get_head(self,L):
    
12.         if len(L) >= 1:
    
13.             return L[0]
    
14.         else:
    
15.             return []
    
16. 
    
17.     def get_tail(self,L):
    
18.         if len(L) >= 1:
    
19.             return L[1:]
    
20.         else:
    
21.             return []
    
22. 
    
23.     def delete(self,X, L):
    
24.         if L == []:
    
25.             return []
    
26.         else:
    
27.             if X == self.get_head(L):
    
28.                 return self.delete(X, self.get_tail(L))
    
29.             else:
    
30.                 return [self.get_head(L)] + self.delete(X, self.get_tail(L))
    

复制代码

风扫地

Seawolf 发表于 2019-6-15 10:56
看不懂你说的异或怎么在你的code里体现，能解释一下吗，我用python写了一个，runtime：60ms

a ^ a = 0;
0 ^ b = b;
a ^ b ^ c = a ^ (b ^ c);
a ^ b ^ c = a ^ c ^ b;

异或操作满足结合律和交换律。
在本题中，出现偶数次的数在异或操作后会变成0，出现奇数次的数会最后剩下来。