136_只出现一次的数字

风扫地

/*
给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。

说明：

你的算法应该具有线性时间复杂度。 你可以不使用额外空间来实现吗？

示例 1:

输入: [2,2,1]
输出: 1
示例 2:
输入: [4,1,2,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[i];
    }
    return ret_val;

}

/*
最近提交结果：
通过
显示详情
执行用时 :12 ms, 在所有C提交中击败了99.46% 的用户
内存消耗 :7.9 MB, 在所有C提交中击败了40.52%的用户


16 / 16 个通过测试用例 状态：通过
执行用时：12 ms
提交时间：0 分钟之前

*/

风扫地

利用异或特性～

Seawolf

看不懂你说的异或怎么在你的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[0]
        else:
            return []

    def get_tail(self,L):
        if len(L) >= 1:
            return L[1:]
        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.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，出现奇数次的数会最后剩下来。