algorithm - 线性时间解决方案

Question

我在面试的时候被问到这个问题。

你站在 0 点，你必须到达位置 X。你可以跳到 D(1 到 D)。如果 X > D，很明显你无法在初始跳跃时到达位置 X。

现在从 1 到 N 每秒都有瓦片出现在随机位置。这是一个零索引数组 A[k]，其中 A[k] 表示瓦片在第 k 秒出现的位置。你必须找出，在哪一秒你有可能到达(或穿越)目的地 X。

如果在初始或 A[0] 之后可能，则返回 0，或返回最小秒数。如果在所有拼贴之后仍然不可能，则返回 -1。

约束: 1 <= N <= 100,000

1 <= D <= 100,000

1 <= X <= 100,000

1 <= A[i] <= X

例如。

X = 7, D = 3

A = {1,3,1,4,2,5}

那么答案是 3。因为在第 3 秒时方 block 出现在位置 4 并且有可能达到 X=7。在那之前的任何一秒都不可能。

我知道这是一个措辞过多的问题，但如果我不能很好地沟通，我绝对可以解决任何问题。

要注意的是，预期时间复杂度为 O(N)，您可以使用额外空间 O(X)。

我找到了一个 O(n * log n * log n) 的解决方案。即二分查找 second 得到 first [1..mid] 元素，按位置排序并验证解决方案。它似乎通过了测试用例，但它不是线性的。

我努力尝试但找不到任何 O(N) 解决方案。你能帮我么？

Answer 1

线性是指瓷砖数量的线性，对吧？

如果是这样，此解决方案(在 Java 中)仅迭代切片数组一次。

在每次迭代中，它还需要迭代 D 和 X 次，但它与瓦片数组的大小成线性关系。

如果它听起来与您正在寻找的相似，请告诉我。

注意:为简化起见，我假设位置“0”处的图 block 在第二个数字“0”时可用，因此有效地将第二个“0”视为您所站的图 block 出现的时间，然后其他图 block 出现在第 1、2 秒等处。

    public class TestTiles {

        public static int calculateSecond(Integer x, Integer d, int[] tiles) {
            // start by making all positions unreachable (false)
            boolean[] posReachable = new boolean[x+1];
            // iterate each second only once
            for (int second = 0; second < tiles.length; second++) {
                int tile = tiles[second];  // this tile is available now
                // so mark all positions from "tile" to "tile + d" reachable
                for (int pos = tile; (pos <= tile + d) && pos <= x; pos++) {
                    posReachable[pos] = true;
                }
                // are all positions reachable now? if so, this is the second to return
                boolean reachable = true;
                for (int pos = 0; pos <= x; pos++) {
                    reachable &= posReachable[pos];
                }
                if (reachable) return second;
            }
            // we can't reach the position
            return -1;
        }

        public static void main(String[] args) {
            System.out.println(calculateSecond(7, 3, new int[]{0,1,3,1,4,2,5}));
            System.out.println(calculateSecond(20, 3, new int[]{0,1,3,1,4,2,5}));
            System.out.println(calculateSecond(2, 3, new int[]{0,1,3,1,4,2,5}));
            System.out.println(calculateSecond(4, 3, new int[]{0,1,3,1,4,2,5}));
            System.out.println(calculateSecond(15, 3, new int[]{0,12,3,9,6}));
        }

    }