[leetcode]268. Missing Number

Missing Number

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

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

Example2:
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?

思路：时间要求为线性，用空间换时间。memset函数将申请的所有空间赋值为0。遍历数组，给数组中存在的值对应的新数组位置赋值为1，再遍历一次新数组，返回值不为1的位置标号即为结果。

问题：一开始想要给新数组赋值为其标号值，但是经过同学修改这样赋值为1更为清晰一些。还遇到了不进入for循环的情况，是memset函数的传入值写的不对。

代码：

int missingNumber(int* nums, int numsSize) {
    int i,j;
    int n= numsSize+1;
    int m= numsSize;
    int *p=NULL;
    int temp;
    int res = -1;
    p=(int *)malloc(n*sizeof(int));
    memset(p,0,sizeof(int)*n);
    
    for(i=0;i<m;i++){
        p[nums[i]]=1;
        }
    
    for(j=0;j<n;j++){
        if(p[j]!=1)
            return j;
    }
    return res;
}