题目

描述

• 从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;
  } 
  }

• 时间复杂度：，遍历一遍数组；
• 空间复杂度：，常数级空间复杂度。

方法二

思路：

• 本题被划分在位运算知识点下，所以也可以考虑使用位运算来寻找缺失数字，且位运算的速度是要快于四则运算的；考虑所有的位运算，容易想到可以使用异或运算来解决问题；
• 异或运算：如果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;
    }
  }

• 时间复杂度：，遍历数组，数量为n；
• 空间复杂度：，常数级空间复杂度。