动画：面试必刷之找出数组中重复的数字

题目

在一个长度为 n 的数组里的所有数字都在 0 - n-1 的范围内。数组中的某些数字是重复的，但不知道有几个数字重复，也不知道重复了几次，请找出数组中任意一个重复的数字。

问题分析

在数组中找出重复数字，第一想到的是暴力破解，首先对数组元素进行排序，然后进行遍历，就可以找出重复的数字。

但是上述性能效率不高，再来想另一种方法，一想到重复，我们最先想到的是散列表是否可以帮助解决数据重复问题。每遍历一个数据，我们就拿到散列表中对比，如果没有，就加入到散列表中，如果有，该数字为重复数字。

第三个方法比较难以想到，题目中说到的是所有数字在 0 - n-1 范围内，所以遍历数组，数组中的每个元素都要和下标对比是否相等，如果是，继续扫描，否则就要和该元素为下标值查找到相同的元素进行比较，如果相同，则为重复数字，否则两个数据进行交换。

动画实现

解题思路

思路一：先进行数据的排序，然后就可以找到重复的数字（但是时间复杂度非常的高）

思路二：散列表（哈希表），一说到查找，首先想到效率最高的就是哈希表。遍历所有的数据，在散列表中查找，如果存在数据，则为重复数字，否则将该数据插入到该哈希表中。（空间复杂度为 O(n)）

思路三：题目中说到的是所有数字在 0 - n-1 范围内，所以遍历数组，数组中的每个元素都要和下标对比是否相等，如果是，继续扫描，否则就要和该元素为下标值查找到相同的元素进行比较，如果相同，则为重复数字，否则两个数据进行交换。

代码实现

javaScript

Java

Python

测试用例

更多相关文章