LeetCode268. 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?

Credits: Special thanks to @jianchao.li.fighter for adding this problem and creating all test cases.

题目的大意是：给你一个数组，里面的元素是从0，1，2，……n这n+1个数字中取出n个来构成的，也就意味着有一个数字是缺失的，你要找到这个数字 题目有个特别要求：你要在O(n)时间复杂度内解决这个问题，并且只能用O(1)的空间复杂度。有的同学就会问这个O(1)的空间复杂度，也就是常量额外空间复杂度是什么，这个就是说你的额外空间必须是常量个，不能跟问题的规模n相关，你可以设置1个int变量也可以设置100个int变量，但是不能用一个长度为跟输入数组长度一样的int数组

分析

既然数组里的元素是从0到n无重复的取，那就用等差数列来算，先算出给定数组所有的数的和，再跟0到n的等差数列的和相比，差的值就是缺失的数字。

class Solution {
public:
    int missingNumber(vector<int>& nums) {
        int i;
        int sum=0;
        int stdSum;
        int size;

        size=nums.size();

        //count sum
        for(i=0;i//count the standard sum
        if(size%2){//odd
            stdSum=(size/2+1)+((size-1)*(size+1))/2;
        }else{//even
            stdSum=(size/2)*(size+1);
        }

        return stdSum-sum;
    }
};

更好的算法

这个我一时还看不懂，有懂的同学欢迎留言分享

public int missingNumber(int[] nums) {

        int rt = nums.length;

        for (int i = 0; i < nums.length; i++) {
            rt = rt ^ nums[i] ^ i;
        }

        return rt;
    }

*来自leetCode 268 Missing Number @_我们的存在