找到消失的数字
思路
一个长度为n的数组中所有数据的范围在[1,n]内，题目要求我们找出在[1,n]范围内，但数组中没有出现的数字
如果可以使用额外空间，那这题就好办了。我们直接创建一个相同大小的数组，数组的每个位置代表[1,n]的每个元素，然后遍历数组计数就行。
我们这里主要讲不利用额外空间，直接在原数组原地修改的方法法。
- 我们先来看一个长度为
n，数据范围在[1,n]内，且没有数字消失的数组[1,2,3,4,5]，那么，我们可以发现，可以利用这些数据的绝对值减一当作下标，使数组的每个位置都变为负数[-1,-2,-3,-4,-5] - 那么再进一步想，如果数组中缺少了
[1,n]中的某一个元素，那么数组当中一定有一个位置的数据不会被置为负数，而这个位置的下标加一，就是我们要找的缺失的元素。 - 注：如果某个位置已经被置为负数了，那就不要管，因为负负得正。
实现代码：
int* findDisappearedNumbers(int* nums, int numsSize, int* returnSize){ int count = 0; //用来记录[1,n]中出现的元素个数 //利用出现的元素将数组的某些位置置为负数 for(int i = 0; i < numsSize; i++) { if(nums[abs(nums[i]) - 1] > 0) { nums[abs(nums[i]) - 1] *= -1; count++; } } *returnSize = numsSize - count; //得到返回数组的大小 int* ret = (int*)malloc(sizeof(int) * (*returnSize)); //申请内存 count = 0; //用来算缺失元素的个数 //找到缺失元素 for(int i = 0; i < numsSize; i++) { if(nums[i] > 0) { ret[count] = i + 1; count++; } } return ret; //返回结果 }
