客官,来嘛,谷歌小菜请你尝尝!

作者:柳行刚

编辑:王抒伟

谷歌面试题

等你来挑战

详情往下看

各位,看招

1

题目描述:

一个大小为n的数组,里面的数都属于范围[0, n-1],有不确定的重复元素,找到至少一个重复元素,要求O(1)空间和O(n)时间

2

题目分析

翻译一下就是:

描述:有一行N个数,这些数都比N小,而且有重复。

要求:让你找到重复的数,满足“O(1)空间和O(n)时间”。

有人可能不理解空间复杂度和时间复杂度

时间复杂度:执行算法所需要的计算工作量

空间复杂度:执行这个算法所需要的内存空间

如果你看到这里可以以迅雷不及掩耳的速度得到解决办法,那么你就离谷歌。。。还很远。

然而这里有大神可以以两种办法解决,请看VCR

3

解法一:

条件1:要求用O(n)的时间复杂度,这意味着只能遍历数组一次。

同时还要寻找重复元素,很容易想到建立哈希表来完成。

完成办法:遍历数组时将每个元素映射到哈希表中,如果哈希表中已经存在这个元素则说明这就是个重复元素

因此直接使用C++ STL中的hash_set(参见《STL系列之六 set与hash_set》)可以方便的在O(n)时间内完成对重复元素的查找。

但是:要求O(1)的空间空间复杂度,因此采用哈希表这种解法肯定在空间复杂度上是不符合要求的。

但可以沿着哈希法的思路继续思考,题目中数组中所以数字都在范围[0, n-1],因此哈希表的大小为n即可。

因此我们实际要做的就是对n个范围为0到n-1的数进行哈希,而哈希表的大小刚好为n。

对排序算法比较熟悉的同学不难发现这与一种经典的排序算法——基数排序非常类似。

而基数排序的时间空间复杂度刚好符合题目要求!

因此尝试使用基数排序来解这道面试题

4

例子详解

下面以2,4,1,5,7,6,1,9,0,2这十个数为例,展示下如何用基数排序来查找重复元素

下标

0

1

2

3

4

5

6

7

8

9

数据

2

4

1

5

7

6

1

9

0

2

(1)由于第0个元素a[0] 等于2不为0,故交换a[0]与a[a[0]]即交换a[0]与a[2]得:

下标

0

1

2

3

4

5

6

7

8

9

数据

1

4

2

5

7

6

1

9

0

2

(2)由于第0个元素a[0] 等于1不为0,故交换a[0]与a[a[0]]即交换a[0]与a[1]得:

下标

0

1

2

3

4

5

6

7

8

9

数据

4

1

2

5

7

6

1

9

0

2

(3)由于第0个元素a[0] 等于4不为0,故交换a[0]与a[a[0]]即交换a[0]与a[4]得:

下标

0

1

2

3

4

5

6

7

8

9

数据

7

1

2

5

4

6

1

9

0

2

(4)由于第0个元素a[0] 等于7不为0,故交换a[0]与a[a[0]]即交换a[0]与a[7]得:

下标

0

1

2

3

4

5

6

7

8

9

数据

9

1

2

5

4

6

1

7

0

2

(5)由于第0个元素a[0] 等于9不为0,故交换a[0]与a[a[0]]即交换a[0]与a[9]得:

下标

0

1

2

3

4

5

6

7

8

9

数据

2

1

2

5

4

6

1

7

0

9

(6)由于第0个元素a[0] 等于2不为0,故交换a[0]与a[a[0]]即交换a[0]与a[2],但a[2]也为2与a[0]相等,因此我们就找到了一个重复的元素——2

下标

0

1

2

3

4

5

6

7

8

9

数据

2

1

2

5

4

6

1

7

0

9

有了上面的分析,代码不难写出:

具体实现代码(C++)

5

解法二:

数组中数据范围为[0,n-1],因此可以通过判断元素是否大于0来决定这个元素是未访问过的数据还是已访问过的数据

通过加n。这样通过判断元素是否大于等于n就能决定这个元素是未访问过的数据还是已访问过的数据。

完整代码如下:

具体实现代码(C++)

原文发布于微信公众号 - 机器学习算法全栈工程师(Jeemy110)

原文发表时间:2017-09-04

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏九彩拼盘的叨叨叨

JavaScript 的变量和数据类型

信息是由数据组成的。变量可以理解成装数据的“盒子”。操作某个数据,首先要做是找到数据所在的盒子(变量)。放在变量里的数据称为变量值。

452
来自专栏深度学习之tensorflow实战篇

python yield函数深入浅出理解

首先关于生成器的那些事: 1.通常的for…in…循环中,in后面是一个数组,这个数组就是一个可迭代对象,类似的还有链表,字符串,文件。它的缺陷是所有数据都...

2834
来自专栏思考的代码世界

Python基础学习04天

1014
来自专栏达摩兵的技术空间

a>b的那些事

经常会遇到对比两个值大小关系的逻辑,常规的处理中我们都是处理两个数字或者数字类型的字符串。那么这里进行延伸拓展的练习,来避免一些开发中的采坑。

511
来自专栏angularejs学习篇

angularjs学习第八天笔记(指令作用域研究)

angularjs其作用域通过scope来实现,其取值有三种情况:true、false、{}

661
来自专栏Vamei实验室

Python深入05 装饰器

装饰器(decorator)是一种高级Python语法。装饰器可以对一个函数、方法或者类进行加工。在Python中,我们有多种方法对函数和类进行加工,比如在Py...

19010
来自专栏desperate633

详解javascript中的即时函数,内部函数,能重写自身的函数即时函数内部函数返回函数的函数能重写自己的函数小结

在上篇谈到匿名函数和回调函数的基础上,我们接着介绍javascript中的即时函数,内部函数,返回函数的函数,能重写自身的函数等几种常见的函数类型及使用方法。只...

671
来自专栏转载gongluck的CSDN博客

sscanf的高级用法 正则表达式

sscanf() - 从一个字符串中读进与指定格式相符的数据。 函数原型: int sscanf( const char *, const char *, ....

3064
来自专栏代码世界

Python之编码

一、Python2与Python3的区别 1、从宏观上考虑,Python2重复代码太多,错误率高,不够规范。Python崇尚的是语言简洁、优美、清晰。Pytho...

27810
来自专栏C/C++基础

C++认识容器的迭代器

假设有个map容器,用于存储大学班级中各个家乡省份对应的学生数,key为省份中文全拼,value为学生数。现需要删除人数为0的记录,删除代码如下:

661

扫描关注云+社区