Найдите средний список неизвестных размеров

В недавнем интервью меня спросили:

Найдите средний элемент отсортированного списка неизвестной длины, начиная с первой позиции.

Я ответил следующим образом:

Имейте 2 счетчика позиции:

счетчик1 Counter2

Увеличить счетчик1 на 1 и счетчик2 на 2. Когда счетчик 2 достигнет конца счетчика 1, он будет посередине. Я чувствую, что это не эффективно, потому что я пересматриваю узлы, которые я уже видел. В любом случае, существует ли более эффективный алгоритм?

Ответ 1

Предполагая связанный список, вы можете сделать это при посещении произвольно близкого к N элемента.

Сделать 5/4 N:

Итерации по списку, пока вы не нажмете на конец, считая элементы.
Снимите якорь при каждой мощности 2-го элемента. Отслеживать последние 2 якоря.
Итерируйте предыдущий якорь, пока он не достигнет середины списка.

Когда вы попадаете в конец списка, предыдущий якорь находится до середины, но, по крайней мере, на полпути. Таким образом, N для полной итерации + не более 1/4 N для якоря = 5/4 N.

Уменьшение якорей более часто, например, при каждой мощности потолка 1.5-го элемента, приближает вас к N по мере необходимости (за счет отслеживания большего количества якорей, но для любого заданного X в качестве шага мощности асимптотическая память постоянна).

Ответ 2

Я предполагаю, что вы обсуждаете связанный список. Действительно, ваше решение отличное. Альтернативой было бы просто пройти список, подсчитывающий количество элементов, а затем начать с самого начала, пройдя половину подсчитанной суммы. Оба метода заканчивают перемещение узлов 3n/2, поэтому нет большой разницы.

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

Ответ 3

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

Затем найдите позицию END_OF_LIST/2.

Таким образом, вам не нужно посещать каждый node.

Ответ 4

Технически вы можете сделать это за один проход, если используете память O (N) (при условии, что вы используете связанный список).

Переместите список и преобразуйте его в массив (указателей, если это связанный список).
Возврат arr [N/2]

Изменить: мне действительно нравится ваш ответ!

Ответ 5

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

// assume non-empty list
slow = fast = first;
count = 0;

while (fast)
{
  fast = fast.next;

  if (!fast)
    break;

  count++;
  fast = fast.next;

  if (fast)
    count++;

  slow = slow.next;
}

if (count % 2)
  return slow.data;
else
  return (slow.data + slow.next.data)/2.0;

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