268. 丢失的数字

一、题目描述

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

二、解题思路

2.1 思路1

既然数值是在 [0, n] 之间，也就是说可以把正确的数值设到数组 num[i] 上。

比如此时 i = 0, nums[i] = 3

那么就知道了 3 是存在的，并把它交换到它应该在的位置。

nums[0] = nums[3];
nums[3] = 3;

通过这样把值设到正确的位置。

最后再遍历一遍数组，如果索引和值不相等，表示当前索引的值丢失了。

2.2 思路2（官方解法）

异或操作中，同一个数值异或1次，得到的结果为 0。

比如 3 ^ 3 = 0。

根据这种现象，可以通过异或数组中的所有值：

0 ^ nums[0] ^ 1 ^ nums[1] ... ^ (n - 1) ^ nums[n - 1] ^ n

在这里面，正常值有2个，它们异或之后结果是 0，而丢失的数字只有一个，所以异或结果就是丢失的数字。

官方解法也太骚了，这还真想不到。。。

三、复杂度分析

1）思路1

• 时间 O(n)
• 空间 O(1)

1）思路2

• 时间 O(n)
• 空间 O(1)

四、参考代码

1）解法1

/**
 * 丢失的数字
 *
 * @param nums 数组
 * @return 丢失的数字
 */
private int missingNumber(int[] nums) {
    int n = nums.length;
    for (int i = 0; i < n; i++) {
        int t = nums[i];
        while (0 <= t && t < n && nums[t] != nums[i]) {
            // 一直交换到正确的位置
            int temp = nums[t];
            nums[t] = nums[i];
            nums[i] = temp;
            t = nums[i];
        }
    }
    for (int i = 0; i < n; i++) {
        if (nums[i] != i) {
            return i;
        }
    }
    return n;
}

2）解法2

/**
 * 丢失的数字（官方解法）
 *
 * @param nums 数组
 * @return 丢失的数字
 */
private int missingNumber2(int[] nums) {
    int missing = nums.length;
    for (int i = 0; i < nums.length; i++) {
        missing ^= i ^ nums[i];
    }
    return missing;
}