链接: 数组中重复的数字
思路一:
运用基数排序的思想,从 nums数组 的第一个元素开始遍历,把每个出现过的数字放到一个新开辟的数组 arr 中去。 若在放入时候发现 arr 中该数字位置已经有一个了,就直接 return nums[i]。 若遍历完了数组还没出现重复的,直接 return -1。
代码:
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。
代码:
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)。