Leetcode

136. Single Number

136. Single Number

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:

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

Example 2:

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

Method1: 排序

分析：要求Run time O(N), Space Complexity: O(1)

==> 考虑Sort the array

Note： Step = 2时，要考虑最后一个数是否可取，确认范围

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution:
    def singleNumber(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        nums.sort()

        for i in range(0, len(nums) - 1, 2):
            if nums[i] != nums[i + 1]:
                return nums[i]

        return nums[-1]

Methos2：Bit Manipulation(XOR)

分析：

  1. $a ⊕ 0 = a$
  2. $a ⊕ a = 0$
  3. $a ⊕ b ⊕ a = (a ⊕ a) ⊕ b = 0 ⊕ b = b$

计算nums里面每一个num ⊕ 运算的结果，最后的值就是the Single number

1
2
3
4
5
6
7
8
9
10
11
12
def singleNumber2(self, nums):
    """
    :type nums: List[int]
    :rtype: int
    """

    a = 0

    for i in nums:
        a ^= i

    return a