1. Question: 268. Missing Number

url : https://leetcode.com/problems/missing-number/

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

Example 1:

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

Example 2:

Input: [9,6,4,2,3,5,7,0,1]Output: 8

Note:

Your algorithm should run in linear runtime complexity. Could you implement it using only constant extra space complexity?

 

2. Solution:

class Solution(object):    def missingNumber(self, nums):        """        :type nums: List[int]        :rtype: int        """        size = len(nums)        for i in range(size):            if nums[i] == size:                continue            while nums[i] != i and nums[i] != size:                if nums[nums[i]] == nums[i]:                    return i                nums[nums[i]], nums[i] = nums[i], nums[nums[i]]        for i in range(size):                        if nums[i] != i:                return i        return size