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

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

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

完结。。。文章来源地址https://www.toymoban.com/news/detail-667177.html


到了这里,关于找到所有数组中消失的数(C语言详解)的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 数据结构与算法教程,数据结构C语言版教程!(第五部分、数组和广义表详解)三

    数组和广义表,都用于存储逻辑关系为“一对一”的数据。 数组存储结构,99% 的编程语言都包含的存储结构,用于存储不可再分的单一数据;而广义表不同,它还可以存储子广义表。 本章重点从矩阵的角度讨论二维数组的存储,同时讲解广义表的存储结构以及有关其广度和

    2024年01月21日
    浏览(48)
  • 数据结构和算法——用C语言实现所有图状结构及相关算法

    本文所有代码均在仓库中,这是一个完整的由纯C语言实现的可以存储任意类型元素的数据结构的工程项目。 首先是极好的工程意识,该项目是一个中大型的CMake项目,结构目录清晰,通过这个项目可以遇见许多工程问题并且可以培养自己的工程意识。 其次是优秀的封装性(

    2024年02月06日
    浏览(222)
  • 【数据结构刷题】消失的数字和轮转数组

    目录 一.消失的数字  方法一:异或全部元素 方法二:利用等差数列求和-该数组全部元素之和。 二.轮转数组 题型1:实现一个函数,可以左旋字符串中的k个字符。 写法1:暴力求解 根据该题写出右旋转 写法2:三步旋转法(左逆序,右逆序,整体逆序)  根据左旋转写右旋转 题型

    2024年02月16日
    浏览(40)
  • 438. 找到字符串中所有字母异位词【异位词-哈希数组】

    438. 找到字符串中所有字母异位词 给定两个字符串 s 和 p,找到 s 中所有 p 的 异位词 的子串,返回这些子串的起始索引。不考虑答案输出的顺序。 异位词 指由相同字母重排列形成的字符串(包括相同的字符串)。 示例 1: 输入: s = “cbaebabacd”, p = “abc” 输出: [0,6] 解释: 起

    2023年04月27日
    浏览(40)
  • 数据结构(C语言):递归算法删除链表中所有值为x的结点

           这个标题为什么要叫“一个递归算法的诞生过程”呢?因为我在写这个算法的时候可谓一波三折,冲破重重Bug最终才得到了正确的算法。        所以在这里我和大家分享一下我写这段代码的整个过程。其中提到的一些问题大家可能写代码的时候也会遇到,所以建议

    2024年02月04日
    浏览(46)
  • 头歌(C语言)-数据结构与算法-数组(共7关)

    任务描述 本关任务:将十个数进行从大到小的顺序进行排列。 相关知识(略) 编程要求 根据提示,在右侧编辑器 Begin-End 处补充代码。 输入 输入十个整数。 输出 以从大到小的顺序输出这个十个数。 测试说明 样例输入: 1 2 3 4 5 6 7 8 9 10 样例输出: 10 9 8 7 6 5 4 3 2 1 代码:

    2024年02月11日
    浏览(42)
  • 数据结构-串-KMP算法详解(Next数组计算)(简单易懂)

    本文章就专讲kmp,暴力匹配就不讲了(我相信能搜索kmp的,暴力匹配算法应该也都了解过了) 为什么网上那么多讲kmp 我还发文章,很多文章我觉得讲的不是太通俗易懂,大多数我看起来都觉得有些懵逼 提示:以下信息来源百度 KMP算法是一种改进的字符串匹配算法,由D.E.K

    2024年02月06日
    浏览(46)
  • C语言数据结构+KMP算法next数组优化计算方法+优化后子串匹配代码实现

    通过我之前那篇KMP算法的讲解,我们可以快速手算KMP算法的next数组,但是之前计算的next数组在一些情况下会有缺陷,比如模式串’aaaab’和主串’aaabaaaab’进行匹配 令模式串指针为j 当第一个元素不匹配时,下一次匹配还是要从模式串的第一个元素与主串匹配,其实我们可以直接写

    2024年02月06日
    浏览(54)
  • 分冶算法 剑指 07 重建二叉树 排序算法:剑指45 把数组排成最小的数 10-I 斐波那契数列

    来记录几个注意事项 1.vector容器里利用find()函数 不同于map(map有find方法),vector本身是没有find这一方法,其find是依靠algorithm来实现的。 所以要包含头文件 另外返回类型并不是int 类型的索引 iterator迭代器类型的 2.关于在vector容器里根据找寻到的位置进行切片,前面为新

    2024年02月15日
    浏览(39)
  • 【算法与数据结构】 C语言实现单链表队列详解

    前面我们学习了队列的顺序表的实现,本节将用单链表实现队列。 队列也可以数组和链表的结构实现, 使用链表的结构实现更优一些,因为如果使用数组的结构,出队列在数组头上出数据,效率会比较低 。下面我们先复习一下队列的基本概念: 队列:只允许在一端进行插入

    2024年04月11日
    浏览(60)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包