Самый быстрый алгоритм для перехода через массив

Ответ 1

Поскольку вы можете выбрать любой x из [1, A [i]], я думаю, есть довольно простое решение:

начинаться с 0:

выберите следующий доступный элемент, из которого вы можете достичь более дальнего элемента. i.e выберите i, которые максимизируют я + A [i + x] для x в [1, A [i]]

пока вы не дойдете до конца списка.

Пример:

{2, 4, 1, 2, 3, 2, 4, 2}

начать с 0

от 0 вы можете добраться до 1 или до 2:

• от 1 вы можете добраться до 4
• от 2 вы можете добраться до 3

поэтому max (0 + A [0 + x]) для я = 1

выбрал 1 от 1 вы можете добраться до 2 3 4:

• от 4 вы можете добраться до 7
• от 3 вы можете добраться до 5
• от 2 вы можете добраться до 3

поэтому max (1 + A [1 + x]) для я = 4

выбрал 4

вы можете достичь 7

остановки

the resulting list is : 

0,1,4,7

Как объясняется в моих комментариях, я думаю, что это O (N), потому что из я вы достигаете я + x + 1 по крайней мере в 2 * x операциях.

"Псевдо"

Вы начинаете с 0 (это оптимально)

то вы выбираете i, которые максимизируют (0 + A [0 + x]) (т.е. максимизируем достижимость для следующего элемента)

из этого я вы можете достичь любого другого элемента, доступного из всех других элементов, достижимых с 0 (это длинное предложение, но это означает: кто может делать больше, может делать меньше, поэтому, если я не оптимален, это как хороший как оптимальный)

Итак, я оптимально

то после этого шаг за шагом это рассуждение доказывает оптимальность метода.

Если кто-то знает, как сформулировать это более математически, не стесняйтесь его обновлять.

Ответ 2

Рассматривайте массив чисел как график, а затем проблема эквивалентна Кратчайшая проблема пути, которая может быть решена в O(|E|+|V|log|V|) используя алгоритм Дейкстры.

E = ∑ чисел.

V = число чисел.

Ответ 3

Используйте свою основную идею, но начинайте с начала и вы можете получить O(n).

Цель состоит в том, чтобы сделать последовательность (A_i1, A_i2, ..., A_ik, ...) такую, что

• позиции 0,1,2,...,ik могут быть достигнуты в k или меньше шагов

• позиции i(k-1)+1, i(k-1)+2, ..., ik не могут быть достигнуты менее чем за k шагов

Базовый блок прост:

i0 = 0
i1 = A[0]

и индуктивная часть не слишком сложна:

i(k+2) = max { A_(ik+1) + ik , A_(ik+1) + ik+1, ..., A_(i(k+1)) + i(k+1) }

Ответ 4

Я пойду против потока и скажу вам, что ваш алгоритм "совершенен".

Он использует динамическое программирование в своей самой чистой форме, и его сложность не так уж плоха. В этом смысле я бы сказал, что, скорее всего, это будет ожидаемо от вас на собеседовании.

Если у вас есть привязка к записям (например, A [i] <= C (N)), то его сложность равна O (N * max (C (N), N)). Например, если все записи меньше K, это O (N).

Использование алгоритма Дейкстры (или, как правило, сокращение проблемы до самой короткой проблемы пути) является разумным, но я оцениваю его за чистым решением DP, поскольку алгоритмы графа сложны (и это могло бы иметь неприятные последствия при интервью, если вас спросили о их).

Обратите внимание, что Dijkstra будет O (N C (N) + N log N) вместо (N вершин и N C (N) ребер). Поэтому, в зависимости от C, вы либо строго лучше, либо равны по сложности.

Ответ 5

Вы могли бы сформулировать его как алгоритм графа (действительно, какая проблема не может быть?). Пусть позиции в массиве - вершины, а возможные адресаты имеют ребро из каждой вершины. В вашем примере вершина 0 будет иметь ребра до 1 и 2, а вершина 1 будет иметь ребра до 2, 3, 4 и 5.

Существует несколько эффективных алгоритмов поиска графа. Например, Dijkstra O(|E| + |V|log|V|), а A * - O(log h*), что лучше, если вы можете придумать хорошую эвристику.

Ответ 6

Решение динамического программирования:

отслеживать для каждого элемента наименьшее количество шагов, которые вы можете получить там и откуда вы пришли. затем просто пройдите через массив и для каждого элемента обновите доступные позиции (от я + 1 до я + a [i]).

{ 2 , 4 , 1 , 2 , 3 , 2 , 4 , 2} 
  0

{ 2 , 4 , 1 , 2 , 3 , 2 , 4 , 2} 
  0   1   1 (num of steps)
      0   0 (source)
  ^         (current position)
{ 2 , 4 , 1 , 2 , 3 , 2 , 4 , 2} 
  0   1   1   2   2   2
      0   0   1   1   1
      ^
{ 2 , 4 , 1 , 2 , 3 , 2 , 4 , 2} 
  0   1   1   2   2   2
          ^
etc...

Это O (n + sum (a [i])).. или немного меньше, вам не нужно выходить за пределы массива.

Ответ 7

Вы можете преобразовать массив в граф и найти кратчайший путь. Вот как должно работать преобразование из массива в граф.

Каждый элемент массива является node. И, основываясь на значении в элементе массива, край, нарисованный между node и другими индексами (узлами), к которым мы можем перейти. Как только мы получим этот график, мы можем найти кратчайший путь, который лучше, чем O (n ^ 2).

http://i.imgur.com/Ih3UP.png

Ответ 8

Мой наивный подход - начиная с самого начала, делая дыхание сначала по всем путям (дочерние узлы A [i + 1].. A [i + n]), сохраняя найденные пути для некоторого массива, а затем получаем кратчайший пути. Конечно, все индексы я + n > length (A) отбрасываются. Таким образом, верхняя граница O (n * min (n, max (A [i = 0..n])) + n) - in должна быть на практике менее квадратичной.

Ответ 9

Здесь небольшая модификация ответа Рики Бобби, которую я покажу, будет оптимальной:

find_shortest_path(A):
    path := [0]
    last := 0
    max_reachable = 0

    while A[last] + last < length(A) :  
        next_hop := x such that max_reachable < x <= A[last] + last and last + A[x] is maximum
        push(path, x)
        max_reachable = A[last] + last
        last := x

    return path

доказательство правильности: Я буду использовать индукцию узлов пути, созданного моим алгоритмом.

свойство, которое я покажу, равно P (i) = ith node моего пути имеет "охват" не меньше i-го node любого оптимального пути

где досягаемость определяется как номер наивысшего node, с которым вы можете перейти от этого node или + бесконечности, если вы можете пройти мимо конца массива

P (0) очевидно.

предположим, что P (k) верно при k >= 0

теперь рассмотрим (k + 1) th node в пути, созданном моим алгоритмом. Поскольку мой алгоритм выбрал node k, чтобы он имел, по крайней мере, тот же доступ, что и для оптимального пути node k, набор узлов, который может быть (k + 1) th node для моего алгоритма, равен надмножество одного и того же для любого оптимального пути. Поскольку мой алгоритм выбирает node с наибольшим достижением, из этого следует, что P (K + 1) истинно.

по индукции, P (k) истинно для всех k (до размера созданного пути).

так как мой алгоритм завершится, как только конец массива достигнет цели, и это произойдет не позже, чем для любого оптимального пути, из этого следует, что путь, созданный моим алгоритмом, является оптимальным.

доказательство оптимальности: каждая ячейка массива рассматривается не более одного раза, поэтому O (n), которая асимптотически оптимальна. Я не думаю, что можно разработать алгоритм, который проверяет меньшее количество ячеек в каждом случае.

Ответ 10

Мой метод: Создайте массив reqSteps, чтобы сохранить количество перемещений, которые принимает вход для выхода.
Начните с конца массива.
Проверьте, может ли вход [i] выйти из массива сам по себе, если да введите 1 в minStep, если нет, сохраните минимум последовательных входных значений [i] + 1. Результат minSteps [0];
Верхний метод не работает для ввода {10, 3, 1, 1, 1, 1, 1, 1, 1, 1, 2, 1};
Это даст 9 в качестве ответа.
Правильный ответ - 2.

public static void arrayHop()
{
        int[] input = { 10, 3, 1, 1, 1, 1, 1, 1, 1, 1, 2, 1 };
        int length = input.length;
        int answer = calcArrayHop(input, length);

}

public static int calcArrayHop(int[] input, int length) {
    int minSteps;
    int[] reqSteps = new int[length];
    for(int i=0;i<length;i++)
        reqSteps[i]=Integer.MAX_VALUE;
    int nextStep;

    for (int i = length - 1; i >= 0; i--) {
        int minsteps = Integer.MAX_VALUE;
        if (i + input[i] >= length) {
            reqSteps[i] = 1;
        } else
        {
            for (int j = i+1; j <= (i + input[i]); j++) {
                if(j>input.length-1)
                    break;
                if (reqSteps[j] < minsteps)
                    minsteps = reqSteps[j];
            }
        reqSteps[i] = minsteps+1;
        }


    }

    return reqSteps[0];
}

}