找到所有数组中消失的数(C语言详解)

简介: 找到所有数组中消失的数(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;
}

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

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

完结。。。


目录
相关文章
|
22天前
|
传感器 算法 安全
【C语言】两个数组比较详解
比较两个数组在C语言中有多种实现方法,选择合适的方法取决于具体的应用场景和性能要求。从逐元素比较到使用`memcmp`函数,再到指针优化,每种方法都有其优点和适用范围。在嵌入式系统中,考虑性能和资源限制尤为重要。通过合理选择和优化,可以有效提高程序的运行效率和可靠性。
70 6
|
25天前
|
存储 缓存 算法
在C语言中,数据结构是构建高效程序的基石。本文探讨了数组、链表、栈、队列、树和图等常见数据结构的特点、应用及实现方式
在C语言中,数据结构是构建高效程序的基石。本文探讨了数组、链表、栈、队列、树和图等常见数据结构的特点、应用及实现方式,强调了合理选择数据结构的重要性,并通过案例分析展示了其在实际项目中的应用,旨在帮助读者提升编程能力。
49 5
|
25天前
|
存储 程序员 编译器
C 语言数组与指针的深度剖析与应用
在C语言中,数组与指针是核心概念,二者既独立又紧密相连。数组是在连续内存中存储相同类型数据的结构,而指针则存储内存地址,二者结合可在数据处理、函数传参等方面发挥巨大作用。掌握它们的特性和关系,对于优化程序性能、灵活处理数据结构至关重要。
|
29天前
|
存储 C语言 计算机视觉
在C语言中指针数组和数组指针在动态内存分配中的应用
在C语言中,指针数组和数组指针均可用于动态内存分配。指针数组是数组的每个元素都是指针,可用于指向多个动态分配的内存块;数组指针则指向一个数组,可动态分配和管理大型数据结构。两者结合使用,灵活高效地管理内存。
|
29天前
|
存储 NoSQL 编译器
C 语言中指针数组与数组指针的辨析与应用
在C语言中,指针数组和数组指针是两个容易混淆但用途不同的概念。指针数组是一个数组,其元素是指针类型;而数组指针是指向数组的指针。两者在声明、使用及内存布局上各有特点,正确理解它们有助于更高效地编程。
|
1月前
|
存储 人工智能 算法
数据结构实验之C 语言的函数数组指针结构体知识
本实验旨在复习C语言中的函数、数组、指针、结构体与共用体等核心概念,并通过具体编程任务加深理解。任务包括输出100以内所有素数、逆序排列一维数组、查找二维数组中的鞍点、利用指针输出二维数组元素,以及使用结构体和共用体处理教师与学生信息。每个任务不仅强化了基本语法的应用,还涉及到了算法逻辑的设计与优化。实验结果显示,学生能够有效掌握并运用这些知识完成指定任务。
54 4
|
2月前
|
存储 编译器 C语言
【c语言】数组
本文介绍了数组的基本概念及一维和二维数组的创建、初始化、使用方法及其在内存中的存储形式。一维数组通过下标访问元素,支持初始化和动态输入输出。二维数组则通过行和列的下标访问元素,同样支持初始化和动态输入输出。此外,还简要介绍了C99标准中的变长数组,允许在运行时根据变量创建数组,但不能初始化。
55 6
|
2月前
|
存储 算法 C语言
C语言:什么是指针数组,它有什么用
指针数组是C语言中一种特殊的数据结构,每个元素都是一个指针。它用于存储多个内存地址,方便对多个变量或数组进行操作,常用于字符串处理、动态内存分配等场景。
|
2月前
|
存储 C语言
C语言:一维数组的不初始化、部分初始化、完全初始化的不同点
C语言中一维数组的初始化有三种情况:不初始化时,数组元素的值是随机的;部分初始化时,未指定的元素会被自动赋值为0;完全初始化时,所有元素都被赋予了初始值。
|
2月前
|
C语言
C语言数组
C语言数组
24 0