c# - 更好的 Frog 穿越算法

Question

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

一只小 Frog 想要到河的另一边。 Frog 当前位于位置 0，想要到达位置 X。树叶从树上掉到河面上。
给定一个非空的零索引数组 A，它由 N 个代表落叶的整数组成。 A[K] 表示在时间 K 时一片叶子落下的位置，以分钟为单位。
目标是找到 Frog 可以跳到河对岸的最早时间。 Frog 只有在河对岸从 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 ，整条河都被覆盖了;)