0136._single_number.md

136. Single Number

难度: Easy

刷题内容

原题连接

• https://leetcode.com/problems/single-number/description/

内容描述

Given a non-empty 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?

Example 1:

Input: [2,2,1]
Output: 1
Example 2:

Input: [4,1,2,1,2]
Output: 4

解题方案

思路 1 - 时间复杂度: O(N)- 空间复杂度: O(N)******

位运算，终于要take it了

非常常见的一道算法题，将所有数字进行异或操作即可。对于异或操作明确以下三点：

• 一个整数与自己异或的结果是0
• 一个整数与0异或的结果是自己
• 异或操作满足交换律，即a^b=b^a

Python的位操作： https://wiki.python.org/moin/BitwiseOperators

class Solution(object):
    def singleNumber(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        res = nums[0]
        for i in nums[1:]:
            res ^= i
        return res