线性时间解决方案

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个第二个图块出现在位置4,所以可以达到X = 7.在此之前的任何一秒都不可能.

我知道这是一个措辞太多的问题,但如果我不能很好地沟通,我绝对可以清除任何事情.

问题是预期的时间复杂度为O(N),您可以使用额外的空间O(X).

我找到了一个O(n*log n*log n)的解决方案.这是二次搜索并获得第一个[1..mid]元素,按位置排序并验证解决方案.它似乎通过了测试用例,但它不是线性的.

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

Answer 1

线性是指与瓷砖数量成线性关系，对吗？

如果是这样，这个解决方案（在 Java 中）只会迭代瓦片数组一次。

在每次迭代中，它还需要迭代 D 次和 X 次，但它相对于图块数组的大小是线性的。

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

注意：为了简化，我假设位置“0”处的图块在第二个数字“0”处可用，因此有效地将第二个“0”视为仅您所站立的图块存在的时间，然后是其他图块存在的时间图块出现在第 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}));
        }

    }