题目:找到所有数组中消失的数
题目详情:
给你一个含 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;
}
以上就是本题的两种解法,其实都不算很复杂,就是得画图得想到这里,如果现在还不具备此思维也不要慌张正常现象而已,多刷题锻炼思维即可;
如有不足之处欢迎来补充交流!文章来源:https://www.toymoban.com/news/detail-667177.html
完结。。。文章来源地址https://www.toymoban.com/news/detail-667177.html
到了这里,关于找到所有数组中消失的数(C语言详解)的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!