谈谈百度一面中的某道题

简介: 该题如下描述:  有101个数,为[1,100]之间的数,其中一个数是重复的,如何寻找这个重复的数,其时间复杂度和空间复杂度是多少?     本人在读了这道题后,顿感惊讶……不可能这么简单哦!难道我哪里想错了? 困惑之下写出我自己想法,希望各位朋友一起讨论一下。

该题如下描述:

 有101个数,为[1,100]之间的数,其中一个数是重复的,如何寻找这个重复的数,其时间复杂度和空间复杂度是多少?

 

  本人在读了这道题后,顿感惊讶……不可能这么简单哦!难道我哪里想错了?

困惑之下写出我自己想法,希望各位朋友一起讨论一下。如果各位发现我哪里想错了,请指出一下,感谢!

解决思路:

  1)如果题中的“数”指整数,那这道题,我觉得太简单了。

    直接把这101 个数相加求出累计和S1;再求出1+2+3+...+100的和S2,然后直接S1-S2就能得出这个重复数是多少。

    时间复杂度应该是n,空间复杂度应该是1

      2)如果题中的“数”指实数,那也比较简单。

   A思路:直接来个二重循环,就能找出来了。如此的话,时间复杂度:n的二次方,空间复杂度:1

            B思路:先排序,再来个一重循环。排序如果用快速或归并之类的,则整个时间复杂度为n(logn),空间复杂度为:n

 

正确答案如何,我就不敢确定了。

 

相关文章
|
6月前
|
存储 前端开发 JavaScript
【面试题】(简单粗暴点)百度一面,直接问痛我
【面试题】(简单粗暴点)百度一面,直接问痛我
|
搜索推荐 UED
做好这几点百度收录很快的
网站质量就是做好网站的基本页面审美度和网站框架,一个好的网站框架,可以让网站能够被客户清晰的认知到底要表达哪些,这也是各大浏览器比较喜欢的网站框架。
|
搜索推荐 程序员
谈一谈|搜索引擎的运用
谈一谈|搜索引擎的运用
76 0
|
JavaScript 开发工具 git
大厂面试-百度
大厂面经-百度
74 0
|
IDE Java Linux
谈谈腾讯和百度的C++开发环境
笔者先后在TB待过,主要做C++开发工作。今天来谈一下两个公司的C++开发环境。
623 0
谈谈腾讯和百度的C++开发环境
|
搜索推荐 UED SEO
谈谈2010年网站百度优化新技术
Html标签的使用、关键词密度和位置、URL命名等页面布局在网站优化中占有很大的权重,尤其对于百度而言,所以学习竞争对手的页面布局再根据自身网页的特点进行修改,你可以省去很多时间,但各自网页的权重是不一样的,所以你不仅要去研究领先的竞争对手,还可以研究一下比自己落后的竞争对手,取其精华、去其糟粕。
129 0
|
XML 搜索推荐 JavaScript
小弟对百度网站排名算法的总结归纳
最近在做深圳人才网的关键字排名,推广写软文的时间很少,所以直接进入主题、
140 0
|
搜索推荐 算法 安全
SEO没有秘籍,不要期待会有一劳永逸的方法
对于从事SEO行业的来说,相信都会有这样的感觉:SEO是一件挺辛苦的工作。要做好SEO,提高网站流量,没有捷径,只有踏踏实实做好基本优化,扩充内容,吸引链接。很多做SEO的都可能会幻想着,有一天能够得到一部SEO秘籍,从而让自己的工作变得轻松,惬意。但SEO没有秘籍,大家也只能是想想罢了。 1、为什么说没有SEO秘籍 有的SEO初学者以为有什么SEO秘籍。经常在<span style="color: rgba(38, 38, 38, 1)"><a rel="dofollow" href="https://www.fgba.net/" title="富贵论坛"><span style="co
172 0
|
SEO 搜索推荐
百度熊掌号SEO指南1.0,seo重点摘录
百度熊掌号seo指南6月6号发布,一直没有时间去研读,今天粗略的看了一下,内容包含对seo的要求,对网站的要求,对运营的支持,和对熊掌号功能的介绍。
972 0