谈谈百度一面中的某道题

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

 

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

 

相关文章
|
7月前
|
存储 前端开发 JavaScript
【面试题】(简单粗暴点)百度一面,直接问痛我
【面试题】(简单粗暴点)百度一面,直接问痛我
|
搜索推荐 UED
做好这几点百度收录很快的
网站质量就是做好网站的基本页面审美度和网站框架,一个好的网站框架,可以让网站能够被客户清晰的认知到底要表达哪些,这也是各大浏览器比较喜欢的网站框架。
|
搜索推荐 程序员
谈一谈|搜索引擎的运用
谈一谈|搜索引擎的运用
80 0
|
JavaScript 开发工具 git
大厂面试-百度
大厂面经-百度
78 0
|
Arthas 监控 IDE
谈谈阿里arthas背后的原理
谈谈阿里arthas背后的原理
谈谈阿里arthas背后的原理
|
IDE Java Linux
谈谈腾讯和百度的C++开发环境
笔者先后在TB待过,主要做C++开发工作。今天来谈一下两个公司的C++开发环境。
635 0
谈谈腾讯和百度的C++开发环境
|
搜索推荐 UED SEO
谈谈2010年网站百度优化新技术
Html标签的使用、关键词密度和位置、URL命名等页面布局在网站优化中占有很大的权重,尤其对于百度而言,所以学习竞争对手的页面布局再根据自身网页的特点进行修改,你可以省去很多时间,但各自网页的权重是不一样的,所以你不仅要去研究领先的竞争对手,还可以研究一下比自己落后的竞争对手,取其精华、去其糟粕。
131 0
|
数据采集 Web App开发 JavaScript
爬虫技术的门道,这篇文章总结的最全
Web是一个开放的平台,这也奠定了Web从90年代初诞生直至今日将近30年来蓬勃的发展。然而,正所谓成也萧何败也萧何,开放的特型、搜索引擎以及简单易学的HTML、CSS技术使得Web成为了互联网领域里最为流行和成熟的信息传播媒介;但如今作为商业化软件,Web这个平台上的内容信息的版权却毫无保证,因为相比软件客户端而言,你的网页中的内容可以被很低成本、很低的技术门槛实现出的一些抓取程序获取到,这也就是这一系列文章将要探讨的话题—— 网络爬虫 。
|
SEO 搜索推荐
百度熊掌号SEO指南1.0,seo重点摘录
百度熊掌号seo指南6月6号发布,一直没有时间去研读,今天粗略的看了一下,内容包含对seo的要求,对网站的要求,对运营的支持,和对熊掌号功能的介绍。
978 0