一个更好的青蛙交叉算法 [英] A Better Frog Crossing Algorithm

问题描述

我从Codility解决以下问题：

I am solving the following problem from Codility:

一个小青蛙想要得到一条河的另一边。青蛙目前位于位置0，并希望得到位置X叶秋从一棵树到江​​面。 您将得到一个非空的零索引数组A由N个整数重新presenting落叶。 A [K]再presents，其中一片叶子落在k时刻的位置，以分钟为单位。 我们的目标是找到最早的时候，青蛙可以跳到河的另一边。青蛙可以跨越，只有当叶出现在河对岸的每个位置，从1至X。

A small frog wants to get to the other side of a river. The frog is currently located at position 0, and wants to get to position X. Leaves fall from a tree onto the surface of the river. You are given a non-empty zero-indexed array A consisting of N integers representing the falling leaves. A[K] represents the position where one leaf falls at time K, measured in minutes. The goal is to find the earliest time when the frog can jump to the other side of the river. The frog can cross only when leaves appear at every position across the river from 1 to X.

我用下面的解决方案，但只拿到一分的81：

I used the following solution but only got a score of 81:

在code是在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）？

My algorithm runs at O(NX). What could be a better algorithm that will only require O(N)?

推荐答案

更​​改code到这样的事情：

Change your code to something like this:

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 (!tiles[internalIndex])
        {
            todo--;
            tiles[internalIndex] = true;
        }

        if (todo == 0)
            return i;
    }

    return -1;
}

这个算法只需要 O（则为a.length）的时间，因为它总是跟踪有多少漏洞，我们还是要填充的叶子。

This algorithm only requires O(A.length) time, since it always keeps track of how many "holes" we still have to fill with leaves.

这是怎么在这里完成？

待办事项是建立叶的桥梁仍然需要叶片数。每当树叶掉下来，我们先检查是否有尚未是叶的位置摔倒。如果没有，我们递减待办事项，填坑，并继续下去。 只要待办事项达到 0 ，整条河被覆盖;）

todo is the number of leaves still required to build the "bridge" of leaves. Whenever a leaf falls down, we first check whether there not already is a leaf at the position it falls down. If not, we decrement todo, fill the hole and go on. As soon as todo reaches 0, the entire river is covered ;)

这篇关于一个更好的青蛙交叉算法的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！