题目描述(简单难度)

0n 中找到缺失的数字。

解法一

最直接的方法,把所有数字存到 HashSet 中,然后依次判断哪个数字不存在。

要注意的是数组的长度其实就等于题目中 0, 1, ..., n 中的 n

public int missingNumber(int[] nums) {
    HashSet<Integer> set = new HashSet<>();
    for (int n : nums) {
        set.add(n);
    }

    //判断 0 到 n 中哪个数字缺失了
    for (int i = 0; i <= nums.length; i++) {
        if (!set.contains(i)) {
            return i;
        }
    }
    return -1;
}

解法二

136 题 的解法二求和做差的方法记忆深刻,这里的话也可以用求和做差。

求出 0n 的和,然后再计算原数组的和,做一个差就是缺失的数字了。

public int missingNumber(int[] nums) {
    int sum1 = 0;
    for (int n : nums) {
        sum1 += n;
    }
    // 等差公式计算 1 到 n 的和
    int sum2 = (1 + nums.length) * nums.length / 2;

    return sum2 - sum1;
}

解法三

又到了神奇的异或的方法了,这里 的解法。

136 题 详细的介绍了异或的一个性质,a ⊕ a = 0,也就是相同数字异或等于 0

这道题的话,相当于我们有两个序列。

一个完整的序列, 0n

一个是 0n 中缺少了一个数字的序列。

把这两个序列合在一起,其实就变成了136 题 的题干——所有数字都出现了两次,只有一个数字出现了一次,找出这个数字。

假如合起来的数字序列是 a b a b c c dd 出现了一次,也就是我们缺失的数字。

如果我们把给定的数字相互异或会发生什么呢?因为异或满足交换律和结合律,所以结果如下。

  a ⊕ b ⊕ a ⊕ b ⊕ c ⊕ c ⊕ d
= ( a ⊕ a ) ⊕ ( b ⊕ b ) ⊕ ( c ⊕ c ) ⊕ d
= 000 ⊕ d
= d

这样我们就找了缺失的数字了。

代码的话,我们可以把下标当成上边所说的完整的序列。因为下标没有 n,所以初始化 result = n

然后把两个序列的数字依次异或即可。

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

解法一和解法二的话都是可以直接想出来,解法三异或的方法其实也不难,但还是没形成惯性,没有往异或思考。

results matching ""

    No results matching ""