# 268.missing-number

## Statement

• Difficulty: Easy
• Tag: `位运算` `数组` `哈希表` `数学` `排序`

``````输入：nums = [3,0,1]

``````输入：nums = [0,1]

``````输入：nums = [9,6,4,2,3,5,7,0,1]

``````输入：nums = [0]

• `n == nums.length`
• `1 <= n <= 104`
• `0 <= nums[i] <= n`
• `nums` 中的所有数字都 独一无二

• Difficulty: Easy
• Tag: `Bit Manipulation` `Array` `Hash Table` `Math` `Sorting`

Given an array `nums` containing `n` distinct numbers in the range `[0, n]`, return the only number in the range that is missing from the array.

Example 1:

``````Input: nums = [3,0,1]
Output: 2
Explanation: n = 3 since there are 3 numbers, so all numbers are in the range [0,3]. 2 is the missing number in the range since it does not appear in nums.
``````

Example 2:

``````Input: nums = [0,1]
Output: 2
Explanation: n = 2 since there are 2 numbers, so all numbers are in the range [0,2]. 2 is the missing number in the range since it does not appear in nums.
``````

Example 3:

``````Input: nums = [9,6,4,2,3,5,7,0,1]
Output: 8
Explanation: n = 9 since there are 9 numbers, so all numbers are in the range [0,9]. 8 is the missing number in the range since it does not appear in nums.
``````

Constraints:

• `n == nums.length`
• `1 <= n <= 104`
• `0 <= nums[i] <= n`
• All the numbers of `nums` are unique.

Follow up: Could you implement a solution using only `O(1)` extra space complexity and `O(n)` runtime complexity?

## Solution

``````from typing import List

class Solution:
def missingNumber(self, nums: List[int]) -> int:
nums = list(map(lambda x: x + 1, nums))
nums.append(1)
nums.append(1)
n = len(nums)
for i in range(n - 2):
x = abs(nums[i])
nums[x] *= -1

for i in range(1, n):
if nums[i] > 0:
return i - 1
``````