Missing Number

https://leetcode.com/problems/missing-number/description/

Given an array containingndistinct numbers taken from0, 1, 2, ..., n, find the one that is missing from the array.

For example, Givennums=[0, 1, 3]return2.

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

Thoughts

由0~n构成的数组少了一个数，让找出丢失的数。这题有多种解法. 可以把应当的sum是多少用高斯法算出来, 再加出来现有sum是多少, 两个一减即Missing的.

Code

class Solution {
    public int missingNumber(int[] nums) {
        int sum = 0;
        for (int i = 0; i < nums.length; i++) {
            sum += nums[i];
        }
        int tsum = 0;
        for (int i = 0; i <= nums.length; i++) {
            tsum += i;
        }

        return tsum - sum;
    }
}

Ver.2

利用xor相同数会消掉的原理, 让nums和0~n xor一下, 剩下的即所求.

/*
 * @lc app=leetcode id=268 lang=cpp
 *
 * [268] Missing Number
 *
 * https://leetcode.com/problems/missing-number/description/
 *
 * algorithms
 * Easy (49.10%)
 * Likes:    1073
 * Dislikes: 1465
 * Total Accepted:    311.6K
 * Total Submissions: 634.1K
 * Testcase Example:  '[3,0,1]'
 *
 * 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?
 */
class Solution {
public:
    int missingNumber(vector<int>& nums) {
        const int N = nums.size();
        int res = 0;
        for (int i = 0; i < N; ++i) {
            res ^= i;
            res ^= nums[i];
        } 
        res ^= N;
        return res;
    }
};

Analysis

时间复杂度O(N), 空间O(1).