题目

给出一个包含 0 .. N 中 N 个数的序列，找出0 .. N 中没有出现在序列中的那个数。

样例
N = 4 且序列为 [0, 1, 3] 时，缺失的数为2。

分析

方法一： 求和法
由于缺失了一个元素，那么我们可以用高斯公式先求出完整的序列的和，然后求出给定数组的和，最后相减就是缺失的元素，效率高

public class Solution {
    /**    
     * @param nums: an array of integers
     * @return: an integer
     */
    public int findMissing(int[] nums) {
        // write your code here
        
        int n = nums.length;
        long sum=0;
        for(int i=0;i<n;i++) {
            sum += nums[i];
        }
        
        return (int) (0.5 * (n+1) * (n) - sum);
    }
}

方法二 交换法

我们已经知道每个位置的元素应该出现的值，那么就遍历一遍数组，如果nums【i】!=i，就把他换到它应该在的位置，最后遍历一遍就得出那个数

public class Solution {
    /**    
     * @param nums: an array of integers
     * @return: an integer
     */
    public int findMissing(int[] nums) {
        // write your code here
        int n = nums.length, i = 0;
        while (i<n) {
            while (nums[i]!=i && nums[i]<n) {
                int t = nums[i];
                nums[i] = nums[t];
                nums[t] = t;
            }
            ++i;
        }
        for (i=0; i<n; ++i)
            if (nums[i]!=i) return i;
        return n;
    }
}