LeetCode_268：缺失数字

题目描述

题目来源：https://leetcode-cn.com/problems/missing-number/
给定一个包含 0, 1, 2, …, n 中 n 个数的序列，找出 0 … n 中没有出现在序列中的那个数。

示例 1:

输入: [0,1]
输出: 2

示例 2:

输入: [9,6,4,2,3,5,7,0,1]
输出: 8

代码

方法一：暴力**法（时间复杂度高）

package leetcode;

import java.util.Arrays;

/**
 * 给定一个包含 0, 1, 2, ..., n 中 n 个数的序列，找出 0 .. n 中没有出现在序列中的那个数。
 */

class Solution {
    public int missingNumber(int[] nums) {
        Arrays.sort(nums);
        int i = 0;
        while (i<nums.length) {
            // 排序后，缺失的数在(n-1)之内
            if(i != nums[i]) {
                return i;
            }
            i++;
        }
        // 排序后，当序列中前(n-1)个数都不缺失时
        return i;
    }
}

// 测试
public class Test {
    public static void main(String[] args) {
        Solution solution = new Solution();
        int[] nums = {0};
        System.out.println(solution.missingNumber(nums));
    }
}

通过 leetcode 测试用例：

方法二：求和（数组和以及（0~n）的和 之差 ——> 缺失的数）（优化了时间复杂度和空间复杂度）

class Solution {
    int missingNumber(int[] nums) {
        int sumNums = 0; // 记录数组的和
        int sumI = 0;    // 记录(0~n)的总和
        int i = 0;
        while (i<nums.length) {
            sumI += i;
            sumNums += nums[i];
            i++;
        }
        
        // sumI = sumI + n
        sumI += i;
        // 两者差即是缺失的序列数
        return (sumI-sumNums);
    }
}

通过 leetcode 测试用例：

方法三：异或（序列中所有的数和i(i=0~n-1)异或，异或完之后得到的数——> 缺失的数）（空间复杂度没有方法二好，但是可以防止数组溢出）

class Solution {
    int missingNumber(int[] nums) {
        int res = nums.length;
        for (int i = 0; i < nums.length; ++i){        
            // 序列中所有的数和i(i=0~n-1)异或，异或完之后得到的数就是缺失的数
            res ^= nums[i];
            res ^= i;
        }
        return res;
    }
}

遍历异或的每一步：

通过 leetcode 测试用例：