Given an array of integers where 1 ≤ a[i] ≤ n (n = size of array), some elements appear twice and others appear once.

Find all the elements of [1, n] inclusive that do not appear in this array.
 Could you do it without extra space and in O(n) runtime? You may assume the returned list does not count as extra space.

Example:
 Input:
 4,3,2,7,8,2,3,1
 Output:5,6

思路分析

讲道理看到题目要求空间复杂度是O(1)时间复杂度是O(n),如果不考虑空间复杂度我们可以采用位对应的方法。举例如下：数组A[n],申请新数组B[n]={0},设置B[A[i] -1] = 1,那么数组B中为0的下标+1就是缺失的元素。
 可是题目中明明要求空间复杂度为O(1),如何实现呢？

完美解法

数组中的值位于1-n,减一之后对应于相应的下标，如果数组中存在比如说5，那么置A[4]的位置的值为负数，这里每次读取数组的值要加绝对值，比如数组中存在两个5，那么第一次设置为负之后，再读取然后减一作为下表时取出的是负数了。然后用求出缺少的数字，申请内存，遍历一遍从原数组中取出。 

/**
 * Return an array of size *returnSize.
 * Note: The returned array must be malloced, assume caller calls free().
 */
int* findDisappearedNumbers(int* nums, int numsSize, int* returnSize) 
{
    if(NULL == nums || numsSize <= 0)
        return NULL;
    int index = 0;
    int exist = 0;
    
    for(int i = 0;i < numsSize;i++)
    {
        index = abs(nums[i]) - 1;
        if(nums[index] > 0)
        {
            nums[index] = - nums[index];
            exist++;
        }
    }
    
    /*缺失的数字个数为*/
    *returnSize = numsSize - exist;
    
    /*申请内存保存缺失的数字*/
    int *result = (int *)malloc(*returnSize * sizeof(int));
    
    for(int i = 0,k = 0;i < numsSize;i++)
    {
        if(nums[i] > 0)
        {
            result[k++] = i + 1;
        }
    }
    return result;
}