leetcode筆記：Missing Number

leetcode筆記：Missing Number

一. 題目描述

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

For example,
Given nums = [0, 1, 3] return 2.

Note:

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

二. 題目分析

題目大意是，給定一個包含從0, 1, 2, ..., n, 選出的n個不同數字的數組，從中找出數組中缺失的那一個數。並給出一個簡單的例子。

題目要求算法能滿足線性時間復雜度和常數空間復雜度。

由於數組中的元素均不相等，且只缺失了一個，因此一種簡單的思路是，求從0到n的等差數列前n項和，減去數組元素累加的和，便可得到缺失的那個數。

若使用位運算，這題與singe number 是一個類型，變形的地方就是首先需要將0, 1, 2, …, n再次放入這個數組。

三. 示例代碼

// 等差數列求和
class Solution {
public:
    int missingNumber(vector& nums) {
        int n = nums.size();
        if (n < 1) return 0;
        int completeSum = n * (n + 1) / 2, currSum = 0;
        for (int i = 0; i < n; ++i)
            currSum += nums[i];
        return completeSum - currSum;
    }
};

// 位運算
class Solution {
public:
    int missingNumber(vector& nums) {
        int ans = 0;
        for (vector::size_type i = 0; i < nums.size(); ++i){
            ans ^= nums[i];
        }
        for (int i = 0; i <= nums.size(); ++i){
            ans ^= i;
        }
        return ans;
    }
};

四. 小結

該題目給定的條件算是比較寬松，比如數值不重復。直接使用等差數列求和法可以快速找到缺失數，只需幾分鐘實現，但沒什麼鍛煉價值；可嘗試使用異或運算來解這道題。