博文中会简要介绍Leetcode P0268题目分析及解题思路。

“Missing Number”是一道较为简单的题目，有多种思路，可以用哈希表记录所有出现过的数，然后再得到未出现的数；也可以用位运算直接获得结果；或者可以通过扫一遍数组，将每个数字归于原位来得到未出现的那个数，即在数组指定位置上出现的数与下标不符。

这里不详述位运算的方法，采用数组变换的思路。时间复杂度是O(n)，而空间复杂度则是O(1)的，同样符合题目要求。

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.

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

以下是Java的题解代码实现。

class Solution {
    public int missingNumber(int[] nums) {
        int N = nums.length, i = 0, missing = N;
        while (i < N) {
            int a = nums[i];
            if (a == i || a == N) {
                missing = (a == N)? i: missing;
                i++;
            }
            else {
                int b = nums[a];
                nums[a] = a;
                nums[i] = b;
            }
        }
        
        return missing;
    }
}

以下是C++的题解代码实现。

class Solution {
public:
    int missingNumber(vector<int>& nums) {
        int N = nums.size(), i = 0, missing = N;
        while (i < N) {
            int a = nums[i];
            if (a == i || a == N) {
                missing = (a == N)? i: missing;
                i++;
            }
            else {
                int b = nums[a];
                nums[a] = a;
                nums[i] = b;
            }
        }
        
        return missing;
    }
};