谈谈百度一面中的某道题

简介: 该题如下描述:  有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

 

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

 

相关文章
|
4月前
|
存储 前端开发 JavaScript
【利用AI刷面试题】50道前端基础面试题(二)
【利用AI刷面试题】50道前端基础面试题
|
4月前
|
存储 人工智能 前端开发
【利用AI刷面试题】50道前端基础面试题(一)
【利用AI刷面试题】50道前端基础面试题
|
4月前
|
存储 前端开发 JavaScript
【面试题】(简单粗暴点)百度一面,直接问痛我
【面试题】(简单粗暴点)百度一面,直接问痛我
|
搜索推荐 UED
做好这几点百度收录很快的
网站质量就是做好网站的基本页面审美度和网站框架,一个好的网站框架,可以让网站能够被客户清晰的认知到底要表达哪些,这也是各大浏览器比较喜欢的网站框架。
|
人工智能 前端开发 小程序
最近很多人都在说 “前端已死”,讲讲我的看法
最近很多人都在说 “前端已死”,讲讲我的看法
127 0
|
JavaScript 开发工具 git
大厂面试-百度
大厂面经-百度
68 0
|
IDE Java Linux
谈谈腾讯和百度的C++开发环境
笔者先后在TB待过,主要做C++开发工作。今天来谈一下两个公司的C++开发环境。
597 0
谈谈腾讯和百度的C++开发环境
|
机器学习/深度学习 人工智能 算法
小白也能搭建深度模型,百度EasyDL的背后你知多少
部署深度学习服务非常困难,因此简单易用的图形化系统就显得极为重要。本文介绍了百度的图形化深度学习系统 EasyDL,用户可以不需要机器学习背景知识而搭建优秀的深度学习服务。本文重点讨论了 EasyDL 系统的技术模块与优势,它大量采用了迁移学习与自动模型搜索,并针对不同的定制化任务学习不同的深度模型。
325 0
小白也能搭建深度模型,百度EasyDL的背后你知多少
|
搜索推荐 UED SEO
谈谈2010年网站百度优化新技术
Html标签的使用、关键词密度和位置、URL命名等页面布局在网站优化中占有很大的权重,尤其对于百度而言,所以学习竞争对手的页面布局再根据自身网页的特点进行修改,你可以省去很多时间,但各自网页的权重是不一样的,所以你不仅要去研究领先的竞争对手,还可以研究一下比自己落后的竞争对手,取其精华、去其糟粕。
123 0
|
XML 搜索推荐 JavaScript
小弟对百度网站排名算法的总结归纳
最近在做深圳人才网的关键字排名,推广写软文的时间很少,所以直接进入主题、
130 0