专业制作网站图片,商务,鞍山网站建设营销,常州自助建站链接#xff1a;
剑指 Offer 03. 数组中重复的数字
题意#xff1a;
如题
解#xff1a;
看到一个很牛的时间复杂度O(n)的原地算法#xff1a;由于数组长度n#xff0c;数组内只有0到n-1#xff0c;那么#xff0c;我们用对应-n到-1表示nums[index]出现过一次…链接
剑指 Offer 03. 数组中重复的数字
题意
如题
解
看到一个很牛的时间复杂度O(n)的原地算法由于数组长度n数组内只有0到n-1那么我们用对应-n到-1表示nums[index]出现过一次-2n到-n-1表示出现两次
具体是怎么做呢我们遍历数组遇到的下标x的数字t对于nums[t]我们就减去n表示t出现了如果tx那它就修改了还没遍历到的数字但是当我们遍历到t的时候如果发现他处于-n到-1的区间那么我们完全可以依靠n还原它的数值使后序操作正常进行如果tx那么就更好说了因为nums[t]已经使用过了可以直接用来标记数字出现
同时我们知道原数组只有0和正数所以当我们要减操作的时候发现原目标nums[t]已经小于0那么t就是答案
实际代码
#includebits/stdc.h
using namespace std;
int findRepeatNumber(vectorint nums)
{int lgnums.size();for(auto num:nums){int tempnum;if(temp0) templg;//还原数值 if(nums[temp]0) return temp;nums[temp]-lg;}return 0;
}
int main()
{vectorint nums;int num;while(cinnum) nums.push_back(num);int ansfindRepeatNumber(nums);coutansendl;return 0;
}限制
2 n 100000
