CodeFight first重复面试挑战 [英] CodeFight firstDuplicate interview challenge

问题描述

根据问题陈述:

写一个具有O(n)时间复杂度和O(1)额外空间的解决方案 复杂.给定一个数组a，其中只包含范围内的数字 从1到a.length，找到第一个重复的数字 第二次出现具有最小索引.换句话说，如果有 超过1个重复的数字，返回第二个数字 事件的索引比另一个事件的第二次出现的索引小 号.如果没有这样的元素，则返回-1

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

我根据约束遵循了我的代码，但仍然遇到时间复杂度错误.这是我的解决方案:

I followed my code according to constraints and still I'm getting time complexity error. Here's my solution:

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

有人可以建议我使用更好的算法，或者该算法有什么问题吗?

Can anyone suggest me better algorithm or whats wrong with this algorithm?

推荐答案

此问题的算法如下:

对于数组中的每个数字a，每次看到该数字，我们都会将a[abs(a[i]) - 1]设为负数.在遍历a时，如果在某个点上发现a[abs(a[i] - 1]为负，则返回a[i].如果我们未找到负数就到达数组的最后一项，则返回-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.

我想，这就是您要达到的目的，但是您可能已经使事情变得过于复杂了.在代码中是:

I feel like, this is what you were trying to get at, but you might have overcomplicated things. In code this is:

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).

This runs in O(n) time, with O(1) space complexity.

这篇关于CodeFight first重复面试挑战的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！