268. 丢失的数字

Posted on Edited on In , ,
转载自Leet Code

题目描述

给定一个包含 [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 中的所有数字都 独一无二

进阶：

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

我的代码 1: 排序

\(T(N) = O(NlogN)\), \(S(N) = O(1)\)

{.line-numbers}
1
2
3
4
5
6
7
8
9
10
11
12
class MySolution268_1 
{
    public int missingNumber(int[] nums)
    {
    	Arrays.sort(nums);
    	
    	for (int i=0; i<nums.length; i++)
    		if (nums[i]!=i)
    			return i;
    	return nums.length;
    }
}

我的代码 2: 数学

\(T(N) = O(N)\), \(S(N) = O(1)\)

{.line-numbers}
1
2
3
4
5
6
7
8
9
10
11
12
class MySolution268_2 
{
    public int missingNumber(int[] nums)
    {
    	int sum = (0+nums.length)*(nums.length+1)/2;
    	
    	int numsSum = 0;
    	for (int num:nums) numsSum+=num;
    	
    	return numsSum-sum;
    }
}

方法: 位运算

\(T(N) = O(N)\), \(S(N) = O(1)\)

由于异或运算(XOR)满足结合律， 并且对一个数进行两次完全相同的异或运算则会得到原来的数， 因此可以通过异或运算得到缺失的数字。

数组nums中有n个数，并且缺失的数字在[0…n]中。 因此我们可以先计算[0…n]的异或值，再将结果对数组nums中的每一个数nums[i]进行一次异或运算。 没有缺失的数字在[0…n]和数组nums中各出现过一次，因此异或之后得到0； 而缺失的数字只在[0…n]中出现了一次，在数组nums中没有出现，因此异或的结果就是这个缺失的数字。

由于[0…n]正好是这个数组nums的下标加上n，因此可以用一次循环完成所有的异或运算。 可以将结果的初始值设为n，再对数组中的每一个数以及它的下标进行一个异或运算。

例如：

\[ \begin{array}{c|lcr} 下标 & 0 & 1 & 2 & 3\\ \hline 数字 & 0 & 1 & 3 & 4 \\ \end{array} \]

\[ \begin{aligned} missing & = 4 \land (0 \land 0) \land (1 \land 1) \land (2 \land 3) \land (3 \land 4) \\ & = (4 \land 4) \land (0 \land 0) \land (1 \land 1) \land (3 \land 3) \land 2 \\ & = 0 \land 0 \land 0 \land 0 \land 2 \\ & = 2 \end{aligned} \]

代码

{.line-numbers}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution268 
{
    public int missingNumber(int[] nums) 
	{
        int missing = nums.length;
        for (int i = 0; i < nums.length; i++) 
		{
            missing ^= i ^ nums[i];
			//missing  = missing ^ (i ^ nums[i])
        }
        return missing;
    }
}