谈谈百度一面中的某道题

简介: 该题如下描述:  有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月前
|
算法 搜索推荐
太厉害了!腾讯T4大牛把《数据结构与算法》讲透了,带源码笔记
经历过校招的人都知道,算法和数据结构都是不可避免的。 在笔试的时候,最主要的就是靠算法题。像拼多多、头条这种大公司,上来就来几道算法题,如果你没AC出来,面试机会都没有。
|
10月前
|
移动开发 前端开发 决策智能
从0到前端大佬终极完全教程-找工作这一篇就够了
从0到前端大佬终极完全教程-找工作这一篇就够了
147 0
|
10月前
|
XML JSON 前端开发
前端知识笔记(十二)———前端面试容易问到的问题总结
前端知识笔记(十二)———前端面试容易问到的问题总结
93 0
|
JavaScript 开发工具 git
大厂面试-百度
大厂面经-百度
84 0
|
IDE Java Linux
谈谈腾讯和百度的C++开发环境
笔者先后在TB待过,主要做C++开发工作。今天来谈一下两个公司的C++开发环境。
668 0
谈谈腾讯和百度的C++开发环境
|
XML JSON 算法
面试 | 卡掉不少人的一道腾讯算法面试题,高手来试试?
算法题目 给定一个不确定的 Json 对象,求 Json 子节点的最大深度(编程语言不限,不可写伪代码)。
面试 | 卡掉不少人的一道腾讯算法面试题,高手来试试?
|
安全 Java 关系型数据库
阿里JAVA开发面试常问问题总结
我的博客:CODE大全:www.codedq.net;业余草:www.xttblog.com;爱分享:www.ndislwf.com或ifxvn.com。 线程与进程进程是可并发执行的程序在某个数据集合上的一次计算活动,也是操作系统进行资源分配和调度的基本单位。线程是操作系统进程中能够并发执行的实体,是处理器调度和分派的基本单位。每个进程内可包含多个可并发执行的线程。线程自己基本不拥有系统资
2123 0
|
SQL Java 数据库连接
9月腾讯、百度、阿里高频的29道SSM框架面试题解析
9月腾讯、百度、阿里高频的29道SSM框架面试题解析