268. Missing Number-蒲公英云

268. Missing Number

/*
 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? 
*/
//思路：先写一个数组，给他赋值，然后将nums排序，之后一一对比，如果有缺少的数，就输出；没有的话就输出下一个。
// 26ms  4.6%
int missingNumber(int* nums, int numsSize) {
    int num[numsSize],i;
    quicksort(nums,0,numsSize-1);//对给定的数组排序
    for(i=0;i<numsSize;i++)//对于新数组赋值
        num[i] = i;
    for(i=0;i<numsSize;i++)//对比两个数组数值
        if(num[i] != nums[i])
            return num[i];
    if(i == numsSize )//如果没有缺失返回下一个数
        return i;
    return;
}
void quicksort(int* nums,int left,int right) 
{ 
    int i,j,t,temp; 
    if(left>right) 
       return; 
    temp=nums[left]; //temp中存的就是基准数 
    i=left; 
    j=right; 
    while(i!=j) 
    { 
                   //顺序很重要，要先从右边开始找 
                   while(nums[j]>=temp && i<j) 
                            j--; 
                   //再找右边的 
                   while(nums[i]<=temp && i<j) 
                            i++; 
                   //交换两个数在数组中的位置 
                   if(i<j) 
                   { 
                            t = nums[i]; 
                            nums[i] = nums[j]; 
                            nums[j] = t; 
                   } 
    } 
    //最终将基准数归位 
    nums[left] = nums[i]; 
    nums[i] = temp; 
    quicksort(nums,left,i-1);//继续处理左边的，这里是一个递归的过程 
    quicksort(nums,i+1,right);//继续处理右边的 ，这里是一个递归的过程 
}