Joyce' Blog
0%

re-num-in-array

发表于 更新于

题目描述

找出数组中重复的数字。

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

题解

可以借助set数据结构，使用它的count()和insert()两个功能：

1
2
3
4
5
6
7
8
9
10
11
12
int findRepeatNumber(vector<int>& nums) {
	//使用set数据结构
	set<int> s;
	for (int i = 0; i < nums.size(); i++)
	{
		if (s.count(nums[i]))
			return nums[i];
		else
			s.insert(nums[i]);
	}
	return 0;
}

另一种时间复杂度更低的解法：

如果没有重复的话，数值i应该在第i个位置上，所以，从前往后遍历数组，当遇到num[i] = m != i时，将nums[i]与nums[m]互换，直到num[i]==i，如果中途遇到相同的值，就立即返回。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
int findRepeatNumber(vector<int>& nums) {
	for (int i = 0; i < nums.size(); i++)
	{
		while (nums[i] != i)
		{
			int m = nums[i];
			if (nums[m] == m)
				return m;
			nums[i] = nums[m];
			nums[m] = m;
		}
	}
	return -1;
}