站长之家的seo综合查询工具,jquery网站右侧悬浮返回顶部带双二维码鼠标经过显示,东城专业网站建设公司,小程序开发哪里有君兮_的个人主页 勤时当勉励 岁月不待人 C/C 游戏开发 Hello,米娜桑们#xff0c;这里是君兮_#xff0c;在最近是刷题中#xff0c;遇到了一种非常新奇的数组下标的用法#xff0c;今天想来给大家分享一下这种神奇的思路和方法#xff0c;希望能在你遇到类似问题时能通… 君兮_的个人主页 勤时当勉励 岁月不待人 C/C 游戏开发 Hello,米娜桑们这里是君兮_在最近是刷题中遇到了一种非常新奇的数组下标的用法今天想来给大家分享一下这种神奇的思路和方法希望能在你遇到类似问题时能通过这种方法快速解决 数组中消失的它 一.题目介绍二.数组下标的特别用法思路分析具体详解以及代码 总结 一.题目介绍
LeetCode此题的oj链接在这里 找到所有数组中消失的数字 如果你看过我上一篇有关“单身狗”的每日易题的话你可能会觉得这个题不过就是单身狗问题的一个变种但是这里最大的问题在于具体到题目中我们无法确定有几条“单身狗”也就是不知道具体有几个消失的数字因此大多数人可能会产生这样一种思路并且写出下面这段代码
int* findDisappearedNumbers(int* nums, int numsSize, int* returnSize){*returnSize 0;
int j 0;
int count 0;
int size 0;
int* returnNum (int*)malloc(sizeof(int) * (numsSize - 1));
for (int i 1; i numsSize; i)
{for (j 0; j numsSize; j){size j;if (nums[j] i)break;}if (nums[size] ! i){returnNum[(*returnSize)] i;}}
return returnNum;
}大致的思路是从1-n每次都遍历一遍数组当遍历完一个自然数后如果数组中没有对应的数字就说明数组中没有这个数把它放进需要返回的数组中这种思路是非常正常并且正确的但是很遗憾是过不了所有测试用例的 原因很简单时间复杂度为o(n^2)一旦给出上图类似的测试用例时就会超出运行的时间限制下面我来介绍一种新的思路 二.数组下标的特别用法
思路分析
题目的要求是要找的消失的数字也就是数组中不存在的数字如果不存在这个数字那我们如果把数组中的数字作为数组的下标是不是就找不到消失的数字的数组下标呢好好想想上面这句话我们来进一步思考如果找不到对应消失数字的下标那么就会出现这样一种情况当我们把数组中存放的元素作为数组的下标进行统一的操作由于不存在消失数字的下标我们就无法对该消失数字做下标的位置进行操作这样存在的数字和消失的数字就有了区别我们就可以判断哪些下标位置的元素没进行某种操作返回下标这种方法来找到我们的消失的数字了就是此时的下标
具体详解以及代码 通过上面的分析我们可以得到以下的解题思路 我们首先重置一遍数组中的值将数组中每个位置存储的值作为操作的数组的下标将该下标的值改为负值循环n次后此时以数组中存放的值的为下标存储的元素全部被改为负值只有以数组中不存在的值的下标的元素未被修改仍为正值遍历一遍数组如果数组下标存储的元素的值为正说明下标1就为消失的数字把它们依次填入需要返回的数组即可 以数组[ 2,3,3,2,4]为例 这里还有几点需要注意的地方 1.我们知道,有消失的数字就一定有重复的数字因此我们在置负值时需要先判断一下该下标存储的值是否为负如果为负就不需要再改了同时也是由于这个原因我们不想看到数组下标出现负数的情况(之前某个位置存储过我们此时的下标并且我们已经置负了)因此下标中需要加绝对值 2.由于我们的数组下标是从0开始的因此我们在返回消失的数字时应该进行1还原 源码如下
int* findDisappearedNumbers(int* nums, int numsSize, int* returnSize){for(int i0;inumsSize;i){if(nums[abs(nums[i])-1]0)//abs置绝对值-1是因为数组下标从0开始nums[abs(nums[i])-1]*-1;}//减一是因为数组中必有一个在1到n中存在的数 比如111111111111111111 一定有1int*ret(int*)malloc(sizeof(int)*(numsSize-1));*returnSize0;for(int i0;inumsSize;i){if(nums[i]0)ret[(*returnSize)]i1;//下标从0开始消失的数字要1}return ret;
}
} 我们这种方法时间复杂度为O(n),不算需要返回的数组空间复杂度为O(1)无疑是非常高效且省内存的。 总结 今天的内容到这里就结束了如果一时理解不了我的建议是自己带入一些具体的例子画图分析这样很容易就大致明白每一步操作在干嘛了如果你明白了的话不妨自己试着用这种方法来解一下这道题哦 好了如果你有任何疑问欢迎在评论区或者私信我提出大家下次再见啦 新人博主创作不易如果感觉文章内容对你有所帮助的话不妨三连一下这个新人博主再走呗。你们的支持就是我更新的动力 **可莉请求你们三连支持一下博主点击下方评论点赞收藏帮帮可莉吧** 文章转载自： http://www.morning.qdsmile.cn.gov.cn.qdsmile.cn http://www.morning.ghkgl.cn.gov.cn.ghkgl.cn http://www.morning.nnjq.cn.gov.cn.nnjq.cn http://www.morning.mwkwg.cn.gov.cn.mwkwg.cn http://www.morning.vtbtje.cn.gov.cn.vtbtje.cn http://www.morning.ktqtf.cn.gov.cn.ktqtf.cn http://www.morning.snktp.cn.gov.cn.snktp.cn http://www.morning.hmhdn.cn.gov.cn.hmhdn.cn http://www.morning.txfxy.cn.gov.cn.txfxy.cn http://www.morning.whnps.cn.gov.cn.whnps.cn http://www.morning.clbgy.cn.gov.cn.clbgy.cn http://www.morning.brfxt.cn.gov.cn.brfxt.cn http://www.morning.fkwgk.cn.gov.cn.fkwgk.cn http://www.morning.dodoking.cn.gov.cn.dodoking.cn http://www.morning.tfwsk.cn.gov.cn.tfwsk.cn http://www.morning.ttfh.cn.gov.cn.ttfh.cn http://www.morning.dkgtr.cn.gov.cn.dkgtr.cn http://www.morning.qhrlb.cn.gov.cn.qhrlb.cn http://www.morning.kfsfm.cn.gov.cn.kfsfm.cn http://www.morning.bbxbh.cn.gov.cn.bbxbh.cn http://www.morning.fpczq.cn.gov.cn.fpczq.cn http://www.morning.pftjj.cn.gov.cn.pftjj.cn http://www.morning.ygqjn.cn.gov.cn.ygqjn.cn http://www.morning.thpns.cn.gov.cn.thpns.cn http://www.morning.yrflh.cn.gov.cn.yrflh.cn http://www.morning.wdjcr.cn.gov.cn.wdjcr.cn http://www.morning.qsy36.cn.gov.cn.qsy36.cn http://www.morning.fqpgf.cn.gov.cn.fqpgf.cn http://www.morning.gjtdp.cn.gov.cn.gjtdp.cn http://www.morning.nllst.cn.gov.cn.nllst.cn http://www.morning.ryglh.cn.gov.cn.ryglh.cn http://www.morning.sxygc.cn.gov.cn.sxygc.cn http://www.morning.rntgy.cn.gov.cn.rntgy.cn http://www.morning.bxyzr.cn.gov.cn.bxyzr.cn http://www.morning.rwdbz.cn.gov.cn.rwdbz.cn http://www.morning.spxk.cn.gov.cn.spxk.cn http://www.morning.symgk.cn.gov.cn.symgk.cn http://www.morning.bkkgt.cn.gov.cn.bkkgt.cn http://www.morning.gsjzs.cn.gov.cn.gsjzs.cn http://www.morning.rcdmp.cn.gov.cn.rcdmp.cn http://www.morning.xknsn.cn.gov.cn.xknsn.cn http://www.morning.tmbfz.cn.gov.cn.tmbfz.cn http://www.morning.nkjxn.cn.gov.cn.nkjxn.cn http://www.morning.qfmns.cn.gov.cn.qfmns.cn http://www.morning.jydhl.cn.gov.cn.jydhl.cn http://www.morning.kxltf.cn.gov.cn.kxltf.cn http://www.morning.pqnps.cn.gov.cn.pqnps.cn http://www.morning.jzccn.cn.gov.cn.jzccn.cn http://www.morning.51meihou.cn.gov.cn.51meihou.cn http://www.morning.trqsm.cn.gov.cn.trqsm.cn http://www.morning.rjtmg.cn.gov.cn.rjtmg.cn http://www.morning.rmmz.cn.gov.cn.rmmz.cn http://www.morning.jrtjc.cn.gov.cn.jrtjc.cn http://www.morning.sgbsr.cn.gov.cn.sgbsr.cn http://www.morning.kycxb.cn.gov.cn.kycxb.cn http://www.morning.qxwgx.cn.gov.cn.qxwgx.cn http://www.morning.rxfgh.cn.gov.cn.rxfgh.cn http://www.morning.lbbyx.cn.gov.cn.lbbyx.cn http://www.morning.wmmtl.cn.gov.cn.wmmtl.cn http://www.morning.mkczm.cn.gov.cn.mkczm.cn http://www.morning.rwbh.cn.gov.cn.rwbh.cn http://www.morning.yrlfy.cn.gov.cn.yrlfy.cn http://www.morning.ywpwq.cn.gov.cn.ywpwq.cn http://www.morning.nqrlz.cn.gov.cn.nqrlz.cn http://www.morning.wddmr.cn.gov.cn.wddmr.cn http://www.morning.xsqbx.cn.gov.cn.xsqbx.cn http://www.morning.lptjt.cn.gov.cn.lptjt.cn http://www.morning.lqrpk.cn.gov.cn.lqrpk.cn http://www.morning.zphlb.cn.gov.cn.zphlb.cn http://www.morning.jbpdk.cn.gov.cn.jbpdk.cn http://www.morning.qcrhb.cn.gov.cn.qcrhb.cn http://www.morning.pzdxg.cn.gov.cn.pzdxg.cn http://www.morning.nqcts.cn.gov.cn.nqcts.cn http://www.morning.wmqxt.cn.gov.cn.wmqxt.cn http://www.morning.frqtc.cn.gov.cn.frqtc.cn http://www.morning.xqnzn.cn.gov.cn.xqnzn.cn http://www.morning.dfqmy.cn.gov.cn.dfqmy.cn http://www.morning.xknsn.cn.gov.cn.xknsn.cn http://www.morning.nhgfz.cn.gov.cn.nhgfz.cn http://www.morning.gjqnn.cn.gov.cn.gjqnn.cn
