谈谈百度一面中的某道题

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

 

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

 

相关文章
|
2月前
|
算法 前端开发 Java
数据结构与算法学习四:单链表面试题,新浪、腾讯【有难度】、百度面试题
这篇文章总结了单链表的常见面试题,并提供了详细的问题分析、思路分析以及Java代码实现,包括求单链表中有效节点的个数、查找单链表中的倒数第k个节点、单链表的反转以及从尾到头打印单链表等题目。
37 1
数据结构与算法学习四:单链表面试题,新浪、腾讯【有难度】、百度面试题
|
7月前
|
移动开发 前端开发 JavaScript
Web前端开发之面试题全解析 一(3),前端面试题背不下来怎么办
Web前端开发之面试题全解析 一(3),前端面试题背不下来怎么办
|
7月前
|
算法 网络协议 NoSQL
百度后端笔试题知识点总结
百度后端笔试题知识点总结
91 0
|
7月前
|
存储 前端开发 JavaScript
【面试题】(简单粗暴点)百度一面,直接问痛我
【面试题】(简单粗暴点)百度一面,直接问痛我
|
7月前
|
移动开发 前端开发 决策智能
从0到前端大佬终极完全教程-找工作这一篇就够了
从0到前端大佬终极完全教程-找工作这一篇就够了
125 0
|
缓存 算法 网络协议
百度后端面试题知识点总结
百度后端面试题知识点总结
214 0
|
JavaScript 开发工具 git
大厂面试-百度
大厂面经-百度
78 0
|
存储 NoSQL Java
这绝对是全网最全的大厂面试题合集 不信你看……
这绝对是全网最全的大厂面试题合集 不信你看……
|
IDE Java Linux
谈谈腾讯和百度的C++开发环境
笔者先后在TB待过,主要做C++开发工作。今天来谈一下两个公司的C++开发环境。
637 0
谈谈腾讯和百度的C++开发环境
|
XML JSON 算法
面试 | 卡掉不少人的一道腾讯算法面试题,高手来试试?
算法题目 给定一个不确定的 Json 对象,求 Json 子节点的最大深度(编程语言不限,不可写伪代码)。
面试 | 卡掉不少人的一道腾讯算法面试题,高手来试试?