136_只出现一次的数字
/*给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。
说明：
你的算法应该具有线性时间复杂度。 你可以不使用额外空间来实现吗？
示例 1:
输入:
输出: 1
示例 2:
输入:
输出: 4
*/
int singleNumber(int* nums, int numsSize){
int ret_val = 0;
int i = 0;
for(i = 0; i <numsSize;i++)
{
ret_val ^= nums;
}
return ret_val;
}
/*
最近提交结果：
通过
显示详情
执行用时 :12 ms, 在所有C提交中击败了99.46% 的用户
内存消耗 :7.9 MB, 在所有C提交中击败了40.52%的用户
16 / 16 个通过测试用例 状态：通过
执行用时：12 ms
提交时间：0 分钟之前
*/
利用异或特性～ 看不懂你说的异或怎么在你的code里体现，能解释一下吗，我用python写了一个，runtime：60ms
class Solution:
def singleNumber(self, L):
head = self.get_head(L)
tail = self.get_tail(L)
if head in tail:
L1 = self.delete(head,tail)
self.singleNumber(L1)
else:
print(head)
def get_head(self,L):
if len(L) >= 1:
return L
else:
return []
def get_tail(self,L):
if len(L) >= 1:
return L
else:
return []
def delete(self,X, L):
if L == []:
return []
else:
if X == self.get_head(L):
return self.delete(X, self.get_tail(L))
else:
return + self.delete(X, self.get_tail(L))
本帖最后由 风扫地 于 2019-6-15 17:54 编辑
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，出现奇数次的数会最后剩下来。
页:
[1]