leetcode-268-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:

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

Example 2:

1
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?

分析

0, 1, 2, ..., n 的和有个公式：

$\sum_{n}^{i=0}=\frac{n(n+1)}{2}$

所以可以先根据公式求和，再减去原数组的和就可以得到缺失的那个数字。时间复杂度是 O(n)，空间复杂度是常数，符合题目的要求。

解决方案1(Java)

1
2
3
4
5
6
7
8
9
10
class Solution {
    public int missingNumber(int[] nums) {
        int expect = nums.length*(nums.length+1) / 2;
        int actual = 0;
        for (int num : nums) {
            actual += num;
        }
        return expect - actual;
    }
}

解决方案2(Python)

利用 Python 的列表-集合转换，集合相减运算可以用一行代码解决这个问题，唔，感觉有作弊嫌疑←_← 这个效率自然是不高的。

1
2
3
4
5
6
7
class Solution:
    def missingNumber(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        return (set(list(range(len(nums)+1))) - set(nums)).pop()

相关问题

(H) First Missing Positive
(M) Single Number
(H) Find the Duplicate Number

题目来源