一种更好的青蛙交叉算法

Question

我正在解决Codility的以下问题:

一只小青蛙想要到达河的另一边.青蛙目前位于0号位置,想要到达位置X.叶子从树上落到河面上.您将获得一个非空的零索引数组A,它由表示落叶的N个整数组成.A [K]表示一片叶子在时间K下降的位置,以分钟为单位测量.目标是找到青蛙可以跳到河的另一边的最早时间.只有当叶子出现在从1到X的河对岸的每个位置时,青蛙才能穿过.

我使用了以下解决方案,但得分只有81分:

代码在C#中.

using System;
using System.Collections.Generic;

class Solution {
    public int solution(int X, int[] A) {
        bool[] tiles = new bool[X];

        for (int i = 0; i < A.Length; i++)
        {
            tiles[A[i] - 1] = true;

            bool complete = true;

            for (int j = 0; j < tiles.Length; j++)
            {
                if (!tiles[j])
                {
                    complete = false;
                    break;
                }
            }

            if (complete)
                return i;
        }

        return -1;
    }
}

我的算法运行在O(NX).什么是更好的算法,只需要O(N)？

Answer 1

将您的代码更改为以下内容:

public int solution(int X, int[] A) 
{
    bool[] tiles = new bool[X];
    int todo = X;

    for (int i = 0; i < A.Length; i++)
    {
        int internalIndex = A[i] - 1;
        if (internalIndex < X && !tiles[internalIndex])
        {
            todo--;
            tiles[internalIndex] = true;
        }

        if (todo == 0)
            return i;
    }

    return -1;
}

这种算法只需要O(A.length)时间,因为它总是跟踪我们仍然需要用叶子填充多少"洞".

这是怎么做到的？

todo是建造叶子"桥梁"所需的叶子数量.每当一个叶子落下,我们首先检查是否有尚未是在位置叶摔倒.如果没有,我们减少todo,填补空洞然后继续.一todo到达0,整条河都被覆盖;)