Leetcode 268 - Missing Number

DocumentsAlgorithms
Algorithms, Leetcode, Python
Catalogue
  1. 1. Question
  2. 2. Analysis
  3. 3. Code

Question

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?

Analysis

因为 nums 的长度就是列表应有的最大值，因此获取列表长度后通过公式 $n(n+1)/2$ 就可以计算出列表应当有的和。用这个和减去列表实际的总和，就可以得出缺少的那一项。这个算法的时间复杂度为 $O(n)$，计算列表长度和列表总和需要遍历列表。空间复杂度为 $O(1)$。

Code

1
2
3
4
5
6
7
8
class Solution(object):
    def missingNumber(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        n = len(nums)
        return n*(n+1)/2 - sum(nums)
Comments