136. Single Number

[qianlei90]

136. Single Number

tags: 印象笔记

[toc]

---

Question

Given an array of integers, every element appears twice except for one. Find that single one.

note

Your algorithm should have a linear runtime complexity. Could you implement it without using extra memory?

Solution

原来的想法是list(set(list_a)) * 2 - list_a，但是这样的空间复杂度好象不是O(1)的，好象用到set的地方就会产生额外的空间（并不确定）。 正确的解法应该是使用异或，异或的特点就是两个值如果相同就是Flase，不相同就是True。

Show me the code

class Solution(object):
    def singleNumber(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        return reduce(lambda x, y: x ^ y, nums)

- 完 -