题目

描述

从0,1,2,...,n这n+1个数中选择n个数，找出这n个数中缺失的那个数，要求O(n)尽可能小。

方法一

思路

题目明确指出所给的数据在0~n之间，且所有数值均只出现一次，而对于数列求和有 $求和公式$ ，
故，可以遍历整个数组求出总和sum1，再借助上述求和公式计算在不缺失数字的情况下的总和sum2，sum2-sum1即为所缺失的数字。

具体步骤

代码如下：

import java.util.*;
public class Solution {
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
* 找缺失数字
* @param a int整型一维数组 给定的数字串
* @return int整型
*/
public int solve (int[] a) {
   // write code here
   int n = a.length;
   // 通过数学公式计算n+1的数列和
   int sum = (n+1)*n/2;
   // 差即为缺少的数
   return sum - sum(a);
}
// 计算所给数组总和
private int sum(int[] a){
   int sum = 0;
   for (Integer i : a){
       sum += i;    
   } 
   return sum;
} 
}

时间复杂度： $O(n)$ ，遍历一遍数组；
空间复杂度： $O(1)$ ，常数级空间复杂度。

方法二

思路：

本题被划分在位运算知识点下，所以也可以考虑使用位运算来寻找缺失数字，且位运算的速度是要快于四则运算的；考虑所有的位运算，容易想到可以使用异或运算来解决问题；
异或运算：如果a、b两个值不相同，则异或结果为1。如果a、b两个值相同，异或结果为0；
所以，在将问题转换成找出数组中只出现一次的数之后，我们可以让数组中的每一个数异或一下，最后会得到一个结果res，res即为缺失的数字.

具体步骤：

参考下图的例子：

代码如下：

import java.util.*;
public class Solution {
  /**
   * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
   *
   * 找缺失数字
   * @param a int整型一维数组 给定的数字串
   * @return int整型
   */
  public int solve (int[] a) {
      // write code here
      int xor = 0;
      for (int i = 0; i < a.length; i++){
          xor ^= a[i] ^ i;
      }
      return xor ^ a.length;
  }
}

时间复杂度： $O(n)$ ，遍历数组，数量为n；
空间复杂度： $O(1)$ ，常数级空间复杂度。

题解 | #缺失数字#

题目

方法一

思路

具体步骤

方法二

思路：

具体步骤：