algorithm - CodeFight first重复面试挑战

Question

根据问题陈述:

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;
}

谁能建议我更好的算法或者这个算法有什么问题？

Answer 1

这个问题的算法如下:

For each number in the array, a, each time we see that number, we make a[abs(a[i]) - 1] negative. While iterating through a, if at some point we find that a[abs(a[i] - 1] is negative, we return a[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)。