3. 数组中重复的数字
题目描述
在一个长度为 n 的数组 nums 里的所有数字都在 0~n-1 的范围内。数组中某些数字是重复的,但不知道有几个数字重复了,也不知道每个数字重复了几次。请找出数组中任意一个重复的数字。
输出结果:
输入:
[2, 3, 1, 0, 2, 5, 3]
输出:2 或 3
解题思路
思路一:将数组中的元素作为键,索引作为值,当add()发生异常时,则返回。这种方式时间复杂度O(n),空间复杂度O(n)
static int FindDuplicateNumber_ex(int[] nums)
{
var length = nums.Length;
int t = 0;
for (int i = 0; i < length; i++)
{
while (nums[i] != i)
{
if (nums[i] == nums[nums[i]])
{
return nums[i];
}
t = nums[i];
nums[i] = nums[t];
nums[t] = t;
}
t = nums[i];
nums[i] = nums[t];
nums[t] = t;
}
return -1;
}
思路二:充分利用题目限定条件,数组长度为n,所有元素都在0~n-1范围内
,这说明,在0~n-1范围内,一定有索引和元素对应,如果一个索引对应多个值,那么这个值就是重复的。时间复杂度O(n),空间复杂度O(1)
算法逻辑如下:
static int FindDuplicateNumber_ex(int[] nums)
{
var length = nums.Length;
int t = 0;
for (int i = 0; i < length; i++)
{
while (nums[i] != i)
{
if (nums[i] == nums[nums[i]])
{
return nums[i];
}
t = nums[i];
nums[i] = nums[t];
nums[t] = t;
}
t = nums[i];
nums[i] = nums[t];
nums[t] = t;
}
return -1;
}