题目描述
给定一个长度为 n+1 的数组nums,数组中所有的数均在 1∼n 的范围内,其中 n≥1。
请找出数组中任意一个重复的数,但不能修改输入的数组。
样例
给定 nums = [2, 3, 5, 4, 3, 2, 6, 7]。
返回 2 或 3。
blablabla
算法1
(暴力枚举) $O(n)$
时间复杂度
参考文献
C++ 代码
class Solution {
public:
int duplicateInArray(vector<int>& nums)
{int a[nums.size()];
memset(a,0,sizeof a);
for(int i=0;i<nums.size();i++)
{if(!a[nums[i]])
{
a[nums[i]]=1;//未重复出现的赋值为1
}
else return nums[i];
}
}
};
算法2
(二分) $O(nlogn)$
blablabla
时间复杂度
参考文献
C++ 代码
class Solution {
public:
int duplicateInArray(vector<int>& nums)
{int l=1;int r=nums.size()-1;
while(l<r)
{int mid=r+l>>1;
int cnt=0;//每一次都要重新查找所以cnt要重新赋值为0;
for(auto x:nums)cnt+=x>=l&&x<=mid;//计算[l,mid]的数的个数
if(cnt>mid-l+1)//如果大于区间的长度说明[l,mid]该区间有重复的数
r=mid;
else l=mid+1;
}
return r;//找到该数
}
};