java - Frog Cross River - 改进使用的数据结构

Question

我试图从礼貌中做这个练习:

一只小 Frog 想要到达河的对岸。 Frog 目前位于位置 0，想要到达位置 X。树叶从树上落到河面上。

给定一个非空的零索引数组 A，它由 N 个表示落叶的整数组成。 A[K]表示一片叶子在时间K落下的位置，以分钟为单位。

目标是找出 Frog 最早能跳到河对岸的时间。只有当从 1 到 X 过河的每个位置都出现树叶时， Frog 才能过河。

写一个函数:

class Solution { public int solution(int X, int[] A); }

给定一个由 N 个整数和整数 X 组成的非空零索引数组 A，返回 Frog 可以跳到河对岸的最早时间。

如果 Frog 永远无法跳到河的另一边，函数应该返回-1。

我的解决方案:

public int solution(int X, int[] A) {

        int[] vDestT = new int[A.length];
        int j = 0;
        // find times where X is visited
        // sort the array vDestT increasing order
        for (int i = 0; i < A.length; i++) {
            if (A[i] == X && i > X - 1) {
                // put times  corresponding to requested destination X in vDestT in an increasing order
                if (j > 0 && i < vDestT[j - 1]) {
                    int temp = vDestT[j - 1];
                    vDestT[j - 1] = i;
                    vDestT[j] = temp;
                } else
                    vDestT[j] = i;
                j++;
            }
        }

        int k = 0;
        while (k < vDestT.length) {
            int remainP = X - 1;
            int remainT = vDestT[k] - 1;
            // check A[0..X-1]
            while (remainT >= remainP) {
                if (A[remainT] < X) {
                    remainP--;
                }
                if (remainP == 0)
                    return vDestT[k];
                remainT--;
            }
            if (remainT < remainP) {
                k++;
                continue;
            }

        }
        return -1;

    }

嗯，这是我想到的第一个解决方案(得到 18/100 分)并且想改进它，所以我有一些问题:- 我应该用哪种结构替换 vDestT？

-我错过了哪些条件(if(A.length<X) and if (A.length == 1 && X==1) 除外)？

编辑:我认为我必须找到 A[i] = X 的所有时间 i，将“i”放入排序数组的递增顺序中。从我命名为 vDestT 的那个数组的第一个元素开始，看看我是否可以在那之前获得所有的 X-1 位置，如果不能检查第二次 A[i] = X 的位置。=> 一个非常复杂的方法，我不知道为什么我确信我应该得到 A[i] = X 的所有时间并对它们进行排序以找到最早的时间。

Answer 1

没有必要存储每个位置的所有时间然后对它们进行排序，因为您只对第一个感兴趣。此外，输入是按时间顺序排列的，因此您可能不需要一直检查到最后。

• 创建一个能够存储 X boolean 值的数据结构，并将它们设置为 false。
• 创建一个计数器变量并将其设置为零。
• 遍历 A，对于每次 i，如果位置 A[i] 的 boolean 值是 false，则将其设置为 true 并递增计数器。
• 一旦计数器等于 X，所有位置都为真，时间 i 就是您的答案。
• 如果在 A 的末尾，计数器小于 X，则某些位置保持为空。

这样，您只需对输入进行一次迭代，然后在 X 到 N 步中找到答案，即线性时间复杂度。