谈谈百度一面中的某道题

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

 

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

 

相关文章
|
Linux 编译器 开发工具
Android内核的编译过程
Android内核的编译过程
291 0
|
机器学习/深度学习 数据可视化 数据挖掘
职场新技能:Python数据分析,你掌握了吗?
职场新技能:Python数据分析,你掌握了吗?
380 0
|
数据采集 机器学习/深度学习 供应链
python基于评论情感分析和回归、arima销量预测的购物网站选品
python基于评论情感分析和回归、arima销量预测的购物网站选品
|
XML 自然语言处理 搜索推荐
使用Luke Lucene进行索引
目录 luke 简介 luke下载及安装 luke 使用 打开luke Overview选项卡 Documents选项卡 search选项卡 Commits选项卡 Plugins选项卡 导出索引为XML 检查索引正确性 总结 1. luke 简介 luke### 是一个用于Lucene/Solr/Elasticsearch 搜索引擎的,方便开发和诊断的 GUI(可视化)工具。
1674 0
EMQ
|
数据采集 存储 人工智能
EMQ 助力构建工业生产数字孪生基础架构
基于EMQ数据基础设施构建的云边工业互联网数据通道,可以轻松地打造厂级信息中心或云上数字孪生平台,有利于数字孪生技术在工业领域的推广和实践。
EMQ
371 0
EMQ 助力构建工业生产数字孪生基础架构
|
存储 数据采集 数据挖掘
|
开发工具
静态IP设置(超详细)
静态IP设置(超详细)
779 0
静态IP设置(超详细)
|
数据采集 Java API
详细说明--使用阿里云接口进行银行卡四要素实名认证
如今随着互联网产业的多元化发展,尤其是互联网金融,O2O,共享经济等新兴商业形式的兴起,企业对实名认证业务的数据形式和数据质量有了更高的需求。如今也衍生出银行卡实名认证业务,通过接口将银行卡号、手机号、身份证号码、姓名上传至阿里云,再与银联系统进行匹配,判断信息的真实性。
271 0
详细说明--使用阿里云接口进行银行卡四要素实名认证
|
前端开发 小程序
小程序canvas使用网络图片真机不显示解决方案----可直接使用案例测试
小程序canvas使用网络图片真机不显示解决方案----可直接使用案例测试
983 0