Linkedlist отслеживать мин в постоянном времени?

Question

РЕДАКТИРОВАТЬ:

Это не так тривиально, как вы думаете.Примите во внимание тот факт, что каждое добавление нового номера выталкивает старое число из связанного списка.

Решение не кажется таким простым, как отслеживание минимального числа с переменной.Что если минимум выталкивается из связанного списка?Тогда что?Откуда вы знаете, что такое новый мин?

Я слышал этот вопрос на собеседовании:

У вас есть связанный список фиксированной длины.

• В момент времени t = 0 связанный список заполняется случайными числами.

• При каждом увеличении во времени один новый номер вводится в начало связанного списка, и один номер выдвигаетсявне хвоста.

• Вам разрешен только ОДИН обход до первого временного интервала.

  • Это означает один обход за все время. Не один раз в каждый момент времени.
    .

• O (1) хранилище.

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

Какой алгоритм мог бы сделать это?

---

Интересное примечание:

Поскольку информации о сложности времени нет, вам разрешено использовать операции сортировки.Тогда единственная проблема: сортировка занимает более одной итерации.

Answer 1

Разъяснения, прежде чем кто-то неправильно поймет мой пост и понизит его.

Во-первых,

O (1) хранилище не то же самое, что один регистрЭто означает постоянное использование пространства.

Во-вторых,

Я собираюсь назвать ваш LL очередью постоянного размера (CSQ).

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

1 op на CSQ

• Выдвиньте 1 элемент во время O (1) CSQ.
• Удалите соответствующий узел из минимальной кучи за O (lg n) время .
• Добавьте соответствующийэлемент к минимальной куче за O (lg n) время .
• Вставьте 1 элемент в CSQ за O (1) и отметьте ссылку на узел кучи, добавленный выше.

Приведенные выше операции гарантируют, что размер кучи всегда будет синхронизирован с размером очереди --hence O (1).Я беру один предел прохождения, чтобы означать, что он должен быть оптимальным, чем простой поиск O (n).Это O(lg n).

Нахождение мин.

Очевидно, O (1).Просто верните голову кучи мин.

Answer 2

Если узел можно определить следующим образом, решение простое:

class Node {
    int data;
    Node next;
    Node prevMin;
}

Answer 3

Итак, в основном это очередь, реализованная в виде связанного списка (поправьте меня, если я ошибаюсь).Чтобы решить эту проблему, я просто изменил бы идею узла.Типичный узел будет иметь следующий указатель и значение.Измените это, чтобы иметь три элемента, nextPointer, value и minSoFar.Если вам не нравится идея изменения дизайна очереди, прочитайте этот алгоритм, и в конце я привел еще одну идею.

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

Голова в 5 и хвост в 13

5 | 7 | 6 | 9| 5 | 13 |

Моя измененная очередь будет содержать такие узлы, как

{5,5} | {7,6} | {6,6} | {9,9} | {13,13} |({nodeVal, minSoFar})

Теперь рассмотрим операцию, добавив 3 в очередь и удалив 13, очередь становится

{3,3} | {5,5} | {7,6} | {6,6} | {9,9} |

Поскольку 3 меньше текущего элемента головки, минимальное значение для элемента головки покаэто его значение

Рассмотрим еще один случай, когда вам нужно добавить 15 в очередь

{15,5} | {5,5} | {7,6} | {6, 6} | {9,9} |

Поскольку 15 больше текущего элемента головки, текущее минимальное значение становится равным 5.

Таким образом, чтобы найти минимальный элемент вочередь / список, все, что вам нужно сделать, это проверить элемент head, и сложность вашего времени будет O (1)

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

Answer 4

Единственное возможное решение, которое я могу найти, - это техническая поддержка:

Так как размер связанного списка фиксирован во время написания, это означает, что N является константой. В этом случае нам технически разрешено хранить вспомогательную структуру, которая является прямой копией связанного списка (возможно, в массиве). Это O (1) хранилище, так как N постоянно.

Answer 5

Я удивлен, что никто не опубликовал это (так что, вероятно, это неправильно), но (псевдокод):

struct abc                                    // sorry for the name :)
{
    int pos
    int num
}
initialize
{
    struct abc min_array[linked_list_length];   // O(1) space

    fill(min_array, linked_list_elements);      // place every element in the array
    sort(min_array);                            // sort in ascending order, the sorting
                                                // compares num
}

insert_element
{
    linked_list.push(value);
    linked_list.pop();

    for each element in min_array {
        element.pos += 1

        if element.pos > linked_list.elementCount then   // this was popped out!
            element.pos = 1;
            element.num = value;
        end if
    }

    sort(min_array);        // as before, sorting compares only num
}

get_min_value
{
    return min_array[0];
}

Answer 6

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

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

Менее наивно, ваш LL также может быть предварительно отсортированной (сортировать при вставке) кучей, в этом случае найтиминимальный элемент может быть O (1) (в зависимости от выбранной структуры).Тем не менее, вставка займет O (n) времени.

Я знаю, что это не отвечает на ваш вопрос, но это действительно звучит как домашнее задание.Используйте это как руководство / справку / помощь по вашей проблеме.:)

Надеюсь, что все решится, и я надеюсь, что помог!