根据问题陈述:
Write a solution with O(n) time complexity and O(1) additional space complexity. Given an array a that contains only numbers in the range from 1 to a.length, find the first duplicate number for which the second occurrence has the minimal index. In other words, if there are more than 1 duplicated numbers, return the number for which the second occurrence has a smaller index than the second occurrence of the other number does. If there are no such elements, return -1
我根据约束遵循我的代码,但我仍然遇到时间复杂度错误。这是我的解决方案:
int firstDuplicate(std::vector<int> a)
{
long long int n = a.size();
int cnt=0;
for(long long int i=0;i<n;i++)
{
//cout<<a[i]<<" "<<cnt<<endl;
if(a[i]==n||a[i]==-n)
{ cnt++;
if(cnt>1)
return n;
}
else if(a[abs(a[i])]<0)
return -a[i];
else
a[a[i]] = -a[a[i]];
}
return -1;
}
谁能建议我更好的算法或者这个算法有什么问题?
最佳答案
这个问题的算法如下:
For each number in the array,
a
, each time we see that number, we makea[abs(a[i]) - 1]
negative. While iterating througha
, if at some point we find thata[abs(a[i] - 1]
is negative, we returna[i]
. If we reach the last item in the array without finding a negative number, we return-1
.
我觉得,这就是您想要达到的目的,但您可能把事情搞得太复杂了。在代码中是这样的:
int firstDuplicate(std::vector<int> a)
{
for (int i = 0; i < a.size(); i += 1)
{
if (a[abs(a[i]) - 1] < 0)
return abs(a[i]);
else
a[abs(a[i]) - 1] = -a[abs(a[i]) - 1];
}
return -1;
}
运行时间为 O(n),空间复杂度为 O(1)。
关于algorithm - CodeFight first重复面试挑战,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/45647307/