丢失的数字

一、题目描述

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

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

提示:

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

二、题目解析

三、参考代码

// 登录 AlgoMooc 官网获取更多算法图解
// https://www.algomooc.com
// 作者:程序员吴师兄
class Solution {
    public int missingNumber(int[] nums) {

        // 定义变量 missing 为零
        int missing = 0;

        // 循环遍历 nums 中的每个数字
        for(int i = 0 ; i < nums.length; i++){

            // 将 nums 中的数字和 1 到 n 这这些数字全部进行异或
            // 由于两个相同的数字进行异或的结果是 0
            // 比如 5 ^ 5 = 0 
            // 又由于任何一个数和 0 进行异或还是它本身
            // 比如 3 ^ 0 = 3
            // 并且,题目中说明 nums 中的所有数字都独一无二
            // 所以,最终 missing 就是那个只出现过一次的数字
            missing = missing ^ nums[i] ^ (i + 1);

        }

        // missing 就是那个丢失的数字,返回就行
        return missing;

    }
}

四、动画理解(没有声音)

发表评论

邮箱地址不会被公开。 必填项已用*标注