面试题03. 数组中重复的数字

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

输入：
[2, 3, 1, 0, 2, 5, 3]
输出：2 或 3
2 <= n <= 100000

桶装法 O(N),S(N）

• 用数组下标来表示元素，数组中存放元素出现的次数。
• 需要定义和数字范围一样大的数组res，对nums数组进行循环，res[nums[i]]+=1，出现和下标一样的元素，数组中值加一。
• 遍历res数组，res[i]>1表示出现重复，进行返回。
• 需要遍历数组O(N)，开辟N长度的空间S(N）

int findRepeatNumber(vector<int>& nums) 
 {
	 int res[100000]={0};
	  res;
	 for(int i = 0;i < nums.size();i++)
	 {
		 res[nums[i]] += 1;
	 }
	 for(int i = 0;i < 100000;i++)
	 {

		 if(res[i]>1)
		 {
			 return i;
		 }
	 }
	 return -1;
 }
 int main()
 {
	 vector<int> a;
	 a.push_back(2);
	 a.push_back(3);
	 a.push_back(1);
	 a.push_back(0);
	 a.push_back(2);
	 a.push_back(5);
	 a.push_back(3);
	 cout<<findRepeatNumber(a);
 }

利用数组特性 O(N) S(1)

• 利用数组性质，因为元素是从0~n-1,表示如果数组长度为5那么元素在[0~4]，这就表示我们进行数组归位绝对不会出现数组非法访问的问题。就像数组长度为5，但元素为10，需要存储到下标为10的位置这种情况是不存在的。
• 我们现在将数组中的元素进行归位，即让下标为0的位置存储元素0，1存储1。
• 我们开始数组循环，如果nums[i]==i，那么表示归位，如果不等于，那么我们把nums[i]放到下标为nums[i]的位置上，进行交换。
• 这样在归位的过程中，如果i位置上已经有了nums[i]，再来一个那么nums[i]重复了。返回nums[i]即可。
  

void swap(int &a,int &b)
{
	int temp;
	temp = a;
	a = b;
	b = temp;
}
int findRepeatNumber(vector<int>& nums) 
{
	for(int i = 0;i < nums.size();)
	{
		if(nums[i] != i)
		{
			if(nums[nums[i]] == nums[i])
			{
				return nums[i];
			}
			swap(nums[i],nums[nums[i]]);
		}
		if(nums[i] == i)//只有相等时，i++
		{
			i++;
		}
	}
	return -1;
}

加油哦！????。