登陆注册
37240300000242

第242章 位图的方法

答案是肯定的。

有一种方法,需要借助位图(bitmap)来实现。

位图是一种简单但是非常有用的数据结构。

你可以用一个数组来表示它,数组元素为0或者1,0代表不存在,1代表存在。

首先,遍历列表,将里面的元素加入位图中,这是一趟线性操作。

接着,从1遍历到100,依次判断当前数字是否存在于位图中。

如果不存在,那就是缺失的编号,直接返回。

这种方式需要同等大小的额外空间,但时间复杂度是很接近线性的。

其实这里也可以使用哈希表,而不使用位图。

但是,哈希表有额外的性能损耗,还是采用更简单的数据结构为好。

想到这里,杨成已经有了三种方法。

但是他有一个疑问:

有没有不需要借助额外内存空间,时间复杂度也能为线性的方法呢?

同类推荐
  • 星域之光

    星域之光

    他是我部下最强的占星师和预言家,推衍出《星辰图》。观摩此图,我预见未来,也回首过往,看见地球之外的另一片星空.......巫神掌控亡灵和诅咒之力,是最强大的死灵法师;魅神是梦境缔造者,她是幻术师;药神也是炼毒能手,毒师......他们都掌控着自己的部落,而我是墨神.......添加星域之光官方QQ群:473250782
  • 棘

    天下大雪,冰河世界;水漫一方,热气冲天;舒一雯一个在校的大学生,偶然得到了一个空间,谁知末日突然造访,看她在末世拼搏的生活鸡飞狗跳
  • 生化末日之英雄连

    生化末日之英雄连

    穿越到生化末日的平行空间,是不是感觉很牛逼?能把《英雄连》游戏召唤出来,是不是感觉更牛逼?手握千军万马,抢个妹子,搅个基什么的,是不是感觉更加牛逼,高大上?那么,我告诉你,土鳖就是土鳖,给你整个世界,也改变不了你土鳖的现实……这是一本以末世为背景的严肃的小白文,写到哪算哪!如果写跑题了,情节不合理?特么忍着……
  • 超级斗士

    超级斗士

    一场白雾中,地球受到了外星生物的攻击,地球环境系的学生张天羽,本将度过无为的一生,但在灾难中却担起了拯救同学的责任。战斗中他发现,人类早已制造出基因战士对抗外星人,而他曾是因考试不合格而被辞退的基因战士。回归基因战士后,张天羽与战友们必须去拯救地球……
  • 金星登陆战

    金星登陆战

    幻想机甲战记小前传。突然接到加入金星战役的我,决定把这作为一个机会。
热门推荐
  • 地修之道

    地修之道

    张凡自从看了玉米熊的《超级拍卖行》之后,就分析这地修是怎样凝聚灵种的,经过几天的分析出来的结果,原来是用后天性生命精元凝聚灵种的,可是没有地修修炼之法,所以又查看了以前看过的小说,从中找了不用修炼之法的凝聚灵种法,那就是可以用辰东写的《遮天》这本小说中找到的,感应生命之轮,又通过生命之轮找到了后天性生命精元,凝聚出了灵种,踏上了地修之旅……为争夺天材地宝的时候,被一群武者围攻而死,穿越到了洪荒世界,因此在洪荒又开始地修之旅……
  • 鼠鼠生威

    鼠鼠生威

    我是一只不平凡的鼠,叫做鼠小小,我有一个奇特的本领,那就是存在感极弱,嘿嘿,这正好让我去偷吃好吃的,呀,朱果,偷偷拿走,银月草,偷偷拿走,那些蠢笨的守护兽根本就没有发现她偷走了东西,实在是太笨了,咦,那家伙为什么一直盯着她,是不是要吃鼠呀!快跑。
  • 妖姬夜珠

    妖姬夜珠

    偶然翻阅旧作,发现17岁那年的雨季以《左传》片段虚构的一个故事格外精彩。《左传》惜字如金,须惜少年时的我也未曾将心爱的故事酝酿成长篇,或许有朝一日,与日渐风化的故事再续前缘。若您有缘看到这个故事,请用心灵和鼠标阅读一朵乱世桃花离奇的一生……
  • 超能宿体

    超能宿体

    天生拥有穿越能力,引来无数爱好者的穿越尝试,更是一大批神秘怪咖,穿来穿去,连一毛钱也不付,你看,这个小妹妹,不仅不付钱,哎!等一下。小妹妹,你不要乱来,我的身体可没有你那个结构,菊花会爆裂的。哎!这些人呀!不好,再等我一下。老大,你练得不是降龙十八掌,是葵花宝典,不要呀!我不想自宫呀!完了,完了,也不知道神医华佗能不能把我大兄弟给接上。
  • 邪魅男友是判官

    邪魅男友是判官

    某天突然发现自己佩戴了二十个年头的玉佩,不见了,随之,一群莫名奇妙或怨或冤的鬼鬼怪怪开始找上门……无奈的看着壁咚自己的艳鬼“大哥我是真的没法帮你啊!你就走吧!”“你是不是看不起我,是不是,信不信我把你捉回去当第八十房小妾……”艳鬼拿鼻子瞪着她。继续无奈摇头……疑似男主的汉子拎着艳鬼的衣领“这女人我已经预定了,你可以走了……”“能不能解释一下预定是什么意思……”
  • 情意绵绵:首席前夫谁怕你

    情意绵绵:首席前夫谁怕你

    我爱的人不是我的爱人,他心里每一寸都属于另一个人。——题记夏安诺最后悔的事情便是因为自己的家势而嚣张,若不是这样,她的男人有岂会跟别人滚床单;而她最庆幸的事情也是因为她的家势而嚣张,若不是这样,她又岂会知道她的男人只是爱上了她的钱!世间上最无力的事情不是看着自己的老公跟他人滚床单,而是,当你还选择原谅的时候,才知道,所有的不堪都是他一手策划。当自己最爱的人拿着刀架在脖子上的时候,她却第一次没有哭......夏安诺对着面前这个跟自己毫无关系的男人一脸媚笑,心却如同嗜血般,早已干涸地没有颜色。“蓝景生,我和你,早无夫妻关系!”
  • 楚天阔

    楚天阔

    “丑丫头”风采薇,活了21年,是平凡得没人记得住的一枚女屌丝。偶尔入职大型网游公司,却在“楚天阔”电游公测上线前夜,跨进了“楚天阔”的虚拟世界。谁也没想到的是,从此,“小疯子”在另一个世界横空出世……
  • 三眼佣兵传说

    三眼佣兵传说

    佣兵,以智慧为基础,勾心斗角,稍有不慎,命归黄泉。佣兵,以灵力为源泉,飞天腾转,遁地挪移,无所不能。佣兵,以异能为力量,无奇不有,夸张新奇,撕裂长空。尹锋,使用号称史上最强大的禁招和神同归于尽。睁开眼时,却发现自己竟然回到了幼年时代?这就是我的最强大的禁招么?最后的时光回溯?给主人重新来过一次的机会?紧紧的握住拳头,上辈子的一切悲剧,都不会在上演了!上辈子给我制造悲剧的人,这辈子我要十倍奉还!!!①群:37083457(500人大群噢!)
  • 海王星卷:地心世界

    海王星卷:地心世界

    探险小龙队从天王石前往海王星,却在靠近海王星的赤道带时遭遇超强风速,飞船被摧毁,五名队员被抛进浩瀚的太空中,降落在离海王星最近的一颗卫星海卫一上。在那里,他们遭遇冰火山的喷发,小龙队员们跌进火山口,在火山底的冰湖里,他们意外闯进了一个神秘的崔顿氏族领地。为了摆脱海王星对自己星球的控制,氏族人准备动用海王石的力量启动海王星地心世界的冰镜,从而改变海王星的时空。
  • 宠妻成狂:女人,乖一点

    宠妻成狂:女人,乖一点

    结婚前一天,她到婚房逮到未婚夫正跟一个金发女人在一起。婚礼当天,她直接转嫁给了未婚夫的病秧子哥哥,摇身一变成了他的嫂子。“弟弟,多谢你替哥将婚礼流程走到了这里,接下来的入洞房环节,就由我亲自来吧!”陆少东淡然地走到苏沐晴身边,与她十指相扣。