找到所有数组中消失的数（C语言详解）

题目：找到所有数组中消失的数

题目详情：

给你一个含 n 个整数的数组 nums ，其中 nums[i] 在区间 [1,n] 内。请你找出所以在 [1,n] 范围内但没有出现在 nums 中的数字，并以数组的形式返回结果。

示例1：

输入：nums = [ 4，3，2，7，8，2，3，1 ]

输出：[ 5，6 ]

 示例2：

输入：nums = [ 1，1 ]

输出：[ 2 ] 

提示：

n=nums.length

1<=n<=105

1<=nums[i]<=n

 

解法一（非原地修改法）

解题思路：

由题可得给定的数组都是在 [1, n] 范围内的数字,由此我们可以定义一个数组 arr 将 [1, n] 按顺序存起来，此时无论什么数它所对应的下标都是本身减一；

然后我们就想啊，arr 的范围大小是包含于 nums 的，而且 nums 里的整数在 arr 里对应的整数的下标都是其整数减一，所以我们可以做标记来解决本题；

遍历 nums 数组，arr 中凡是在 nums 中出现过的整数都做标记-----记为0，最后 arr 数组中不为0的数字就是消失的数字；

思路实现：

定义数组 arr 并赋值；

    int i=0;int arr[100000]={0};for(i=0;i<numsSize;i++){arr[i]=i+1;}

然后遍历 nums 数组，找到 arr 中与之相对应的数的下标，并将此下标处的数记为0，比如：nums[2]=4，则 arr 中对应 4 的下标为 nums[2] -1=3，然后arr[nums[2] -1]=0；

    for(i=0;i<numsSize;i++){arr[nums[i]-1]=0;}

创建一个动态内存变量 ret ，用来存放消失的数字；

遍历 arr 数组不为0的就是消失的数字并存放在 ret 中；

    int* ret=(int*)malloc(4*numsSize);int k=0;for(i=0;i<numsSize;i++){if(arr[i]>0){ret[k++]=arr[i];}}

此时 ret 中存放的数字就是消失的数字了，返回 ret 即可；

源代码：

int* findDisappearedNumbers(int* nums, int numsSize, int* returnSize){int* ret=(int*)malloc(4*numsSize);int i=0;int arr[100000]={0};for(i=0;i<numsSize;i++){arr[i]=i+1;}for(i=0;i<numsSize;i++){arr[nums[i]-1]=0;}int k=0;for(i=0;i<numsSize;i++){if(arr[i]>0){ret[k++]=arr[i];}}* returnSize=k;return ret;
}

解法二（原地修改法）

解题思路：

其实跟解法一有异曲同工之妙，就是在解法一的基础上不使用 arr 数组，自身解决，一样的意思的，解法一它后面侧重判断的点是 arr 的数值，而我们解法二是原地修改，侧重的是下标的数值，具体如何，听博主慢慢分晓；

在数组 nums 中，有着 n 个数字，数字之间可能会重复，一旦重复就会产生消失的数字，此时我们将数组 nums 的数值与下标分离开来，然后遍历 nums ，然后将下标为 nums[i]-1的值加上 n ，如果 nums[i]-1大于 n，需要对其取模来还原出他本来的值；

然后在创建动态内存变量 ret 来存储消失的数字，遍历数组 nums ，如果数字不大于n，则此下标加一就是消失的数字的；

思路实现：

遍历数组 nums ，将下标为 nums[i]-1的值加上 n，如果此值大于 n ，需要对其取模来还原，即将下标为（nums[i]-1)%n 的值加上 n；

    int i=0;for(i=0;i<numsSize;i++){nums[(nums[i]-1)%numsSize]+=numsSize;}

创建一个动态内存变量 ret ，用来存放消失的数字；

遍历 nums 数组不大于 n 的数字的下标加一就是消失的数字；

    int* ret=(int*)malloc(4*numsSize);int i=0;int k=0;for(i=0;i<numsSize;i++){if(nums[i]<=numsSize){ret[k++]=i+1;}}

此时 ret 中存放的数字就是消失的数字了，返回 ret 即可；

源代码：

int* findDisappearedNumbers(int* nums, int numsSize, int* returnSize){int* ret=(int*)malloc(4*numsSize);int i=0;for(i=0;i<numsSize;i++){nums[(nums[i]-1)%numsSize]+=numsSize;}int k=0;for(i=0;i<numsSize;i++){if(nums[i]<=numsSize){ret[k++]=i+1;}}* returnSize=k;return ret;
}

以上就是本题的两种解法，其实都不算很复杂，就是得画图得想到这里，如果现在还不具备此思维也不要慌张正常现象而已，多刷题锻炼思维即可；

如有不足之处欢迎来补充交流！

完结。。。

---