Missing Number

题目描述

Given an array containing n distinct numbers taken from 0, 1, 2, ..., n, find the one that is missing from the array.

For example, Given nums = [0, 1, 3] return 2.

解题方法

XOR

• 1-n的XOR
• 现有array的XOR

Solution

class Solution(object):
    def missingNumber(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        length = len(nums)
        full = 0
        for i in range(length+1):
            full = full ^ i

        XOR = nums[0]
        for i in range(1, length):
            XOR = XOR ^ nums[i]

        return full ^ XOR

Reference