Leetcode 268. Missing Number

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

For example, Given nums = [0, 1, 3] return 2.

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

两种做法，

1. 求和一个个减去；

2. 在discuss看到的，异或，下标和数字会出现两次，缺少的数字一定是最后的结果，awesome

代码语言：javascript复制

class Solution {
public:
    int missingNumber(vector<int>& nums) {
        int sum = (nums.size()   1) * nums.size() / 2;
        for(auto a : nums) sum -= a;
        return sum;
    }
};

代码语言：javascript复制

public int missingNumber(int[] nums) { //xor
    int res = nums.length;
    for(int i=0; i<nums.length; i  ){
        res ^= i;
        res ^= nums[i];
    }
    return res;
}

distinct numbers return runtime space

0 人点赞