LeetCode.268.Missing Number 连续数组中缺失的数

题目描述

268 Missing Number https://leetcode-cn.com/problems/missing-number/

Given an array containing n distinct numbers taken from 0, 1, 2, ..., n, find the one that is missing from the array.

Example 1:

Input: [3,0,1]
Output: 2

Example 2:

Input: [9,6,4,2,3,5,7,0,1]
Output: 8

Note: Your algorithm should run in linear runtime complexity. Could you implement it using only constant extra space complexity?

解题过程

第一想法是求和 sum(1...n) = n(n+1)/2 再减去数组和，但可能有溢出的风险。 看题解知道可以用异或，时间复杂度 O(n)，空间复杂度 O(n)

private static class SolutionV2020 {
    public int missingNumber(int[] nums) {
        int res = 0;
        for (int i = 0; i < nums.length; i++) {
           res ^= nums[i];
           res ^= i+1;
        }
        return res;
    }
}

GitHub代码

algorithms/leetcode/leetcode/_268_MissingNumber.java https://github.com/masikkk/algorithms/blob/master/leetcode/leetcode/_268_MissingNumber.java