找出数组中任一重复的数字
在一个长度为 n 的数组 nums 里的所有数字都在 0～n-1 的范围内。数组中某些数字是重复的，但不知道有几个数字重复了，也不知道每个数字重复了几次。请找出数组中任意一个重复的数字。
示例 1：
输入：[2, 3, 1, 0, 2, 5, 3]
输出：2 或 3
# python
class Solution:
def findRepeatNumber(self, nums):
# 时间复杂度太高，O(N2)
nums_set = set(nums)
for i in nums_set:
for j in nums:
if i == j:
nums.remove(j)
break
# nums包含所有重复元素
return nums[0]时间复杂度：
空间复杂度：
// java
public int findRepeatNumber(int[] nums) {
Arrays.sort(nums);
int n = nums.length;
int result = 0;
for (int i = 0; i < n - 1; i++) {
if (nums[i] == nums[i + 1]) {
result = nums[i];
break;
}
}
return result;
}# python
nums.sort()
for i in range(len(nums)-1):
if nums[i] == nums[i+1]:
return nums[i]python list sort() 基于排序算法Timsort，时间复杂度为：
，空间复杂度为：
python sort函数内部实现原理
时间复杂度：
空间复杂度：
基于HashSet，依次遍历数组元素，插入集合中，如果无法插入，则为重复元素。
HashSet集合：不允许存储重复的元素，查询速度快
算法步骤
// 效率较低
public int findRepeatNumber(int[] nums) {
Set<Integer> set = new HashSet<Integer>();
int repeat = 0;
for (int i: nums) {
if (!set.add(i)){
repeat = i;
break;
}
}
return repeat;
}时间复杂度：
空间复杂度：
算法步骤:
public int findRepeatNumber(int[] nums) {
HashSet<Integer> set = new HashSet<Integer>();
for (int i: nums) {
// 判断元素是否存在
if (set.contains(i)) {
return i;
}
set.add(i);
}
return -1;
}
}set.contains()、set.add()时间复杂度为O(N)
Java：Set 的 contains() 方法 时间复杂度
时间复杂度是：O(n)
空间复杂度是：O(n)
原地置换算法详解及其应用
每个元素都有自己的位置（该元素的下标，如元素0的位置应该是下标为0），如果一组数（元素个数为n，元素值范围为：[0,n-1]）中缺失或重复，则表现为有空位或位置重复匹配
// java
public int findRepeatNumber4(int[] nums) {
// 判断数组为空是否需要？
if (nums.length == 0){
return -1;
}
for (int i = 0; i < nums.length; i++) {
while (nums[i] != i){
if (nums[i] == nums[nums[i]]){
return nums[i];
}
int temp = nums[i];
nums[i] = nums[temp];
nums[temp] = nums[i];
}
}
return -1;
}TODO：分析
时间复杂度：
空间复杂度：
# python转写
if len(nums) == 0:
return -1
for i in range(len(nums)):
while nums[i] != i:
if nums[i] == nums[nums[i]]:
return nums[i]
temp = nums[i]
nums[i] =nums[temp]
nums[temp] = temp
return -1