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

 

示例 1：

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

示例 2：

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

示例 3：

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

示例 4：

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

 

提示：

  • n == nums.length
  • 1 <= n <= 104
  • 0 <= nums[i] <= n
  • nums 中的所有数字都 独一无二

 

进阶：你能否实现线性时间复杂度、仅使用额外常数空间的算法解决此问题?

Related Topics
  • 位运算
  • 数组
  • 哈希表
  • 数学
  • 排序

  • 👍 579
  • 👎 0

    • 异或、求和 & 【看起来没人用的其实也能用的 原地交换 ！！】

    都知道的异或、求和先贴下、其他还有哈希表，重构数组遍历等等，没啥好说的了，大家都看很多遍了

    异或
    class Solution {
    public int missingNumber(int[] nums) {
        int num = 0;
        for (int i = 0; i < nums.length; i++) {
            num ^= nums[i];
            num ^= i;
        }
        num ^= nums.length;
        return num;
    }
}
    求和
    class Solution {

    public int missingNumber(int[] nums) {
        int num = 0;
        for (int i = 0; i < nums.length; i++) {
            num -= nums[i];
            num += i;
        }
        num += nums.length;
        return num;
    }

}

    丢失数字之类的还有一种会用到原地交换的解法

    这里我们其实也可以尝试下。大促晚值班摸鱼，来玩点花样

    原地交换

    跟官方题解写一样缺少乐趣，毕竟是简单题，能玩的花样一遍都比较多，

    拿官方例题来分析下，第一行对应为数组下标，第二行数原始数组，

    1. 如果nums[i] == nums.length原地交换会越界，那么我就声明一个变量用来保存存放在这个位置的数字，这样我们就可以顺利使用原地交换了，毕竟要求时间O(n),空间O(1)
    • 其实你也可以声明一个长度为nums.length+1的数组来处理，这样可以省事，不过空间就不是O(1)了
    1. 原来第n位上的数字不存在，那就在代码里用-1表示，图里用x表示
    2. 从0下标开始交换，把0交换给n，此时记录丢失数字为0 ,missing = 0;
    3. 后面从下标1开始交换，一直交换这些比较简单省略，直到到下标1上的值为x了，记录当前丢失数字missing = 1;
    4. 后面继续交换，直到最后下标8上的值为x,记录missing = 8;
    5. 结束

    同时，看下剑指offer03的数组中的重复数字这题，试着用原地交换的方法来理解下，或许对你能有帮助
    【原地交换】图解，看个明白

    原地交换代码
    class Solution {

    public int missingNumber(int[] nums) {
        //丢失的
        int misssing = nums.length;
        //额外占用的第nums.length下标位
        int n = -1;
        for (int i = 0; i < nums.length; i++) {
            if (nums[i]==nums.length){
                n = nums[i];
                nums[i] = -1;
            }
            while (nums[i] != -1 && nums[i] != i ){
                swap(nums,i,nums[i]);
                if (nums[i]==nums.length){
                    n = nums[i];
                    nums[i] = -1;
                }
            }
            if (nums[i]==-1){
                misssing = i;
            }
        }
        return misssing;
    }
    
    public void swap(int[] nums, int x, int y){
        int tmp = nums[x];
        nums[x] = nums[y];
        nums[y] = tmp;
    }

}