LeetCode算法题（数组相关）（九）——丢失的数字

问题：

给定一个包含 [0, n] 中 n 个数的数组 nums ，找出 [0, n] 这个范围内没有出现在数组中的那个数。

输入：nums = [3,0,1]
输出：2
解释：n = 3，因为有 3 个数字，所以所有的数字都在范围 [0,3] 内。2 是丢失的数字，因为它没有出现在 nums 中。

输入：nums = [0,1]
输出：2
解释：n = 2，因为有 2 个数字，所以所有的数字都在范围 [0,2] 内。2 是丢失的数字，因为它没有出现在 nums 中。

算法：

这道题目也简单的，我的思路就是创建一个新数组，新数组的长度等于给定数组长度加1，我画个示意图如下：

这是我们的第一步。第二步就是赋值，赋值的具体算法如下图：

对于给定数组，如上图，我们把nums数组中的9赋值给新数组下标为9的位置。剩下的以此类推，这样肯定会剩下一个元素没被赋值，那么没被赋值的肯定就是丢失的数字。java中，数组如果没有被赋值默认是0，因此只要判断，除了下标为0的位置，看看还有没有其他位置的元素是0，如果有，那么就是丢失的数字，如果没有，那么0就是丢失的数字。

实现：

class Solution {
    public int missingNumber(int[] nums) {
        int len = nums.length;
        int [] n = new int[len+1];
        for(int i = 0;i<len;i++){
            n[nums[i]] = nums[i];
        }
        int k,rs=0;
        for(k = 1;k<len+1;k++){
            if(n[k]==0){
                rs = k;
            }
        }
        return rs;
    }
}