题目
在一个长度为 n 的数组 nums 里的所有数字都在 0～n-1 的范围内。数组中某些数字是重复的，但不知道有几个数字重复了，也不知道每个数字重复了几次。请找出数组中任意一个重复的数字。
测试样例
输入：
[2, 3, 1, 0, 2, 5, 3]
输出：2 或 3
限制
2 <= n <= 100000
题解
题解一：遍历
对vector容器中的数值进行逐个遍历，并把检查过的数值在数组中标记出来，如果数值已经被标记过则返回该值。
int findRepeatNumber(vector<int>& nums) {
int a[1000010]={0};
int n = nums.size();
vector<int>::iterator it;
for (it = nums.begin(); it != nums.end(); it++){
if(a[*it] > 0)
return *it;
else
a[*it]++;
}
return -1;
}题解二：原地算法
首先理解每个萝卜都只有唯一的属于自己的坑。因为每个数值只能出现一次，一旦出现多次就要输出该值，那么我们把索引和数值对应起来，比如：nums[0]的位置就对应着0这个数值，一旦在nums[0]的位置出现了数值k，那么就交换nums[0]和nums[k]，保证数值k和其位置对应。
再来说程序的问题。我们有三种情况：
- 要么数值和位置对应，不用做改变，继续向后遍历即可；
- 要么数值和位置不对应，要进行交换，但是在交换的过程中还要判断你要找的位置是不是已经有对应的萝卜占了（在这一步不能持续向后遍历，只有第一种情况才能挪动指针）；
- 如果已经有同样符合要求的数值在那个对应的位置了，那么就说明该值重复了，输出该值！举个例子：
nums={0, 1, 2, 1}
其中nums[0], nums[1]=1, nums[2]=2，这些都是没有问题的，但是nums[3]却不等于3，其数值为1，那么就找1对应的nums[1]，结果发现nums[1]已经等于1了，那么这个时候就说明nums[3]位置的数值1重复了。
- 如果要交换的位置同样不匹配，那么交换就好了。举个例子：
nums={1, 2, 1}
nums[0]=1，那么就直接找nums[1]位置，nums[1]位置也不是对应的数值1，那么直接交换即可，交换后为：nums={2，1，1}。
int findRepeatNumber(vector<int>& nums) {
int n=nums.size(), i=0;
while(i<n){
if(nums.at(i)==i){//符合要求
i++;
continue;
}
else if(nums.at(i)==nums.at(nums.at(i)))
return nums.at(i);
else
swap(nums.at(i), nums.at(nums.at(i)));
}
return -1;
}题解三：快速排序
对数值排个序，连续重复的就是要输出的点。
int findRepeatNumber(vector<int>& nums) {
sort(nums.begin(), nums.end());
int n=nums.size(), temp=nums[0];
for(int i=1; i!=n; i++)
if(temp==nums[i])
return temp;
else
temp=nums[i];
return -1;
}题解四：哈希表
把数值挨个放入哈希表中，出现重复就输出。
int findRepeatNumber(vector<int>& nums) {
unordered_set<int> s;
int n=nums.size(), t=0;
for(int i=0;i!=n;i++){
t=nums[i];
if(s.count(t)==0)
s.insert(t);
else
return t;
}
return -1;
}创作不易，点个赞再走嘛(*^_^*)