这道题用STL容器就很好写了，可以用set也可以用map,
用unordered_map的C++代码如下：
class Solution {
public:
int findDuplicate(vector<int>& nums) {
unordered_map<int, int> m;
int res;
for(int i=;i<nums.size();i++){
if(m.count(nums[i])){
res=nums[i];break;
}
m[nums[i]]=i;
}
return res;
}
};12ms beat 44%
使用set:
class Solution {
public:
int findDuplicate(vector<int>& nums) {
set<int> s;
int res;
for(int i=;i<nums.size();i++){
if(s.find(nums[i])!=s.end()){
res=nums[i];break;
}
s.insert(nums[i]);
}
return res;
}
};16ms beat 33%
C++ 二分法：
但是，但是，但是，题目要求time O(n2) space O(1) 说明这道题要时间换空间，那么使用二分法：
timeO(nlog(n)) spaceO(1): 1 2 2 3 5 4对于某个数x，如果小于等于他的数出现次数大于他，说明重复数在【low，x】之间，如小于等于2的数有3个，那么重复数在【1，2】之间；小于等于1的数只有1个，那么在【2,2】之间，从而得解
class Solution {
public:
int findDuplicate(vector<int>& nums) {
//二分法
/*理论分析，所有的数出现的次数总和加起来为n+1==len,计mid=(low+high)/2;那么当小于mid出现次数大于mid时，则重复数在mid左边*/
int len=nums.size();
int low=,high=len-;
while(low<high){
int mid=low+(high-low)/,cnt=;
for(int num:nums)
if(num<=mid) cnt++;
if(cnt>mid)
high=mid;
else
low=mid+;
}
return low;
}
};快慢指针：
class Solution {
public:
int findDuplicate(vector<int>& nums) {
int n=nums.size()-;
if(n<) return ;
int slow = nums[];
int fast = nums[nums[]];
//vector<int> fs={fast},ss={slow},ts;
while (slow != fast)
{
slow = nums[slow];
fast = nums[nums[fast]];
//fs.push_back(fast);
//ss.push_back(slow);
}
int target=;
while (target != slow){
slow=nums[slow];
target=nums[target];
//ts.push_back(target);
//ss.push_back(slow);
}
/*
cout<<"fs: ";
for(int n:fs)
cout<<n<<",";
cout<<endl;
cout<<"ss: ";
for(int n:ss)
cout<<n<<",";
cout<<endl;
cout<<"ts: ";
for(int n:ts)
cout<<n<<",";
cout<<endl;*/
return target;
}
};