谈谈百度一面中的某道题

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

 

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

 

相关文章
|
5月前
|
算法 前端开发 Java
数据结构与算法学习四:单链表面试题,新浪、腾讯【有难度】、百度面试题
这篇文章总结了单链表的常见面试题,并提供了详细的问题分析、思路分析以及Java代码实现,包括求单链表中有效节点的个数、查找单链表中的倒数第k个节点、单链表的反转以及从尾到头打印单链表等题目。
61 1
数据结构与算法学习四:单链表面试题,新浪、腾讯【有难度】、百度面试题
|
10月前
|
算法 网络协议 NoSQL
百度后端笔试题知识点总结
百度后端笔试题知识点总结
100 0
|
10月前
|
存储 移动开发 前端开发
前端面试题目小结 之一(精选10题)
前端面试题目小结 之一(精选10题)
|
10月前
|
存储 前端开发 JavaScript
【面试题】(简单粗暴点)百度一面,直接问痛我
【面试题】(简单粗暴点)百度一面,直接问痛我
直击灵魂!美团大牛手撸并发原理笔记,由浅入深剖析JDK源码
并发编程这四个字想必大家最近都在网上看到过有很多的帖子在讨论。我们都知道并发编程可选择的方式有多进程、多线程和多协程。在Java中,并发就是多线程模式。而多线程编程也一直是一个被广泛而深入讨论的领域。如果遇到复杂的多线程编程场景,大多数情况下我们就需要站在巨人的肩膀上利用并发编程框架——JDK Concurrent包来解决相关线程问题。
|
IDE Java Linux
谈谈腾讯和百度的C++开发环境
笔者先后在TB待过,主要做C++开发工作。今天来谈一下两个公司的C++开发环境。
668 0
谈谈腾讯和百度的C++开发环境
|
设计模式 Web App开发 移动开发
前端学习之路,分享给刚学或想学前端的网友(持续更新中)
  经常会在群里或论坛上看到有人问:“学习前端有什么捷径?”,一般都是卖油翁式的回答:“无他唯手熟尔”。那么该如何让手熟练呢?其实也就是该如何系统的学习前端。在本文中,我会结合自身的经历,分享一下自己学习前端的过程,期间会穿插引用我过去各个阶段所写的博文。
|
XML JSON 算法
面试 | 卡掉不少人的一道腾讯算法面试题,高手来试试?
算法题目 给定一个不确定的 Json 对象,求 Json 子节点的最大深度(编程语言不限,不可写伪代码)。
面试 | 卡掉不少人的一道腾讯算法面试题,高手来试试?
|
大数据
|
前端开发
最新前端初中级面试题合集一,你确定不看一看嘛
收集的前端面试题,适合低中级前端工程师,祝大家找到好的工作.