0268._missing_number.md

268. Missing Number

难度: Easy

刷题内容

原题连接

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

内容描述

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?

解题方案

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

等差数列前n项和减去数组之和,一行瞬秒 (注意题目input从0开始取值)

class Solution(object):
    def missingNumber(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        return len(nums) * (len(nums) + 1) / 2 - sum(nums)

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

位运算（异或运算）

class Solution(object):
    def missingNumber(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        res = n = len(nums)
        for i in range(n):
            res ^= i
            res ^= nums[i]
        return res

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

让每一个元素都放在正确的index上面，感谢微信上大神 Jay kay的思路，这样写只要给出的nums是非负的就行，应用性更强， 但是这个代码还是无法用于leetcode 41题：First missing positive

最后元素不等于其index的就是返回值

class Solution(object):
    def missingNumber(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        if not nums or len(nums) == 0:
            return 0
        if len(nums) == 1:
            return 1 if nums[0] == 0 else 0
        for i in range(len(nums)):
            tmp = nums[i]
            while tmp < len(nums) and nums[tmp] != tmp:
                nums[tmp], tmp = tmp, nums[tmp]
        for i in range(len(nums)):
            if nums[i] != i:
                return i
        return len(nums)