毕节网站建设兼职连云港北京网站建设

链接：

剑指 Offer 03. 数组中重复的数字

题意：

如题

解：

看到一个很牛的时间复杂度O(n)的原地算法：由于数组长度n，数组内只有0到n-1，那么，我们用对应-n到-1表示nums[index]出现过一次，-2n到-n-1表示出现两次

具体是怎么做呢，我们遍历数组，遇到的下标x的数字t，对于nums[t]我们就减去n，表示t出现了，如果t>x那它就修改了还没遍历到的数字，但是当我们遍历到t的时候，如果发现他处于-n到-1的区间，那么我们完全可以依靠+n还原它的数值，使后序操作正常进行，如果t<x那么就更好说了，因为nums[t]已经使用过了，可以直接用来标记数字出现

同时，我们知道原数组只有0和正数，所以当我们要减操作的时候，发现原目标nums[t]已经小于0，那么t就是答案

实际代码：

#include<bits/stdc++.h>
using namespace std;
int findRepeatNumber(vector<int>& nums)
{int lg=nums.size();for(auto& num:nums){int temp=num;if(temp<0) temp+=lg;//还原数值 if(nums[temp]<0) return temp;nums[temp]-=lg;}return 0;
}
int main()
{vector<int> nums;int num;while(cin>>num) nums.push_back(num);int ans=findRepeatNumber(nums);cout<<ans<<endl;return 0;
}

限制：

• 2 <= n <= 100000