链接: 数组中重复的数字
思路一：
运用基数排序的思想，从 nums数组 的第一个元素开始遍历，把每个出现过的数字放到一个新开辟的数组 arr 中去。 若在放入时候发现 arr 中该数字位置已经有一个了，就直接 return nums[i]。 若遍历完了数组还没出现重复的，直接 return -1。
代码：
代码语言：javascript复制class Solution {
public:
int findRepeatNumber(vector<int>& nums) {
int n = nums.size();
//用vector创建一个数组arr并初始化为0
vector<int> arr(n, 0);
int i = 0;
while(i < n)
{
//若arr中该位置还没出现过则该位置加一
if(arr[nums[i]] != 1)
{
arr[nums[i]] = 1;
i ;
}
//若出现重复了直接return nums[i]
else
{
return nums[i];
}
}
return -1;
}
};这种方法虽然看起来比较直观，但是空间复杂度是为O(N)的。
思路二：
使用原地交换的方法。题目中说到：在一个长度为 n 的数组 nums 里的所有数字都在 0～n-1 的范围内 。说明若存在重复，就会有 一对多的情况 。 所以我们可以这样做：
1、用一个变量 i 做下标，从 nums数组 的第一个元素开始遍历。
2、判断一下 nums[i] 与 nums[nums[i]] 是否相同，若相同则说明是重复的，直接返回 nums[i]。
3、若不相同，则 交换两个位置的元素 ，然后判断一下 nums[i] 会不会等于 i ，会的话说明已经与下标匹配上了，才让 i 。
4、若遍历完说明没有重复的，返回-1。
代码：
代码语言：javascript复制class Solution {
public:
int findRepeatNumber(vector<int>& nums) {
int i = 0;
while(i < nums.size())
{
if(nums[i] == i)
{
i ;
continue;
}
if(nums[i] == nums[nums[i]])
{
return nums[i];
}
else
{
swap(nums[i], nums[nums[i]]);
}
}
return -1;
}
};这样子的题解的空间复杂度为O(1)，时间复杂度为O(n)。
