数组中重复的数字

题目描述：

找出数组中重复的数字。

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

示例 1：

输入：
[2, 3, 1, 0, 2, 5, 3]
输出：2 或 3 

限制：

2 <= n <= 100000

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/shu-zu-zhong-zhong-fu-de-shu-zi-lcof

1、暴力求解

• 时间复杂度是 O(n^2)
• 空间复杂度是 O(1)

2、借助HashSet

• 时间复杂度是 O(n)
• 空间复杂度是 O(n)

将数组中的元素存储到HashSet集合中，借助于HashSet集合的方法判断元素是否重复，集合中存在的话就返回该元素，不存在的话就返回-1.

3、数组代替哈希表

 将nums数组中存储的元素的大小作为bucket数组的下标，然后将nums数组的下标存储到bucket数组中。也就是说如果nums数组中存在相同的元素就会在bucket中存在“碰撞”，

 时间复杂度和空间复杂度都是O(n)

4、最优解法

（1）数组中没有重复元素的

数组初始化：

 交换数组中的元素：

（2）数组中存在重复元素的情况

数组中重复的数字

原文：https://www.cnblogs.com/zhai1997/p/13629509.html