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

Учитывая массив int, каждый int отображается точно TWICE в массив. найти и вернуть int так, что эта пара int имеет max расстояние между собой в этом массиве.

Используйте hashmap, ключ a[i], а значение - индекс. Сканируйте a[], поместите каждое число в хэш. Если число попадает дважды, используйте его индекс минус индекс старых чисел и используйте результат для обновления значения элемента в хэше.

После этого сканируйте хэш и верните ключ с наибольшим элементом (расстояние). это O (n) во времени и пространстве.

Как это сделать в O (n) времени и O (1) пространстве?

Ответы

Ответ 1

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

[2, 1, 1, 3, 2, 3]
Check if 2 == 3?
Store a map of numbers and position: [2 => 1, 3 => 6]
Check if 1 or 2 is in [2 => 1, 3 => 6] ?

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

Ответ 2

Установить индекс iLeft для первого элемента, индекс iRight ко второму элементу. Инкремент iRight index, пока вы не найдете копию левого элемента или не встретите конец массива. В первом случае - помните расстояние.

Увеличение iLeft. Начните поиск с нового iRight. Начальное значение iRight никогда не будет уменьшено. Код Delphi:

  iLeft := 0;
  iRight := 1;

  while iRight < Len do begin //Len = array size
    while (iRight < Len) and (A[iRight] <> A[iLeft]) do
      Inc(iRight); //iRight++
    if iRight < Len then begin
      BestNumber := A[iLeft];
      MaxDistance := iRight - iLeft;
    end;
    Inc(iLeft); //iLeft++
    iRight := iLeft + MaxDistance;
  end;

Ответ 3

Этот алгоритм является O (1) пространством (с некоторым изменением), O (n) time (average), требует, чтобы исходный массив был не const и уничтожал его в конце. Также он ограничивает возможные значения в массиве (три бита каждого значения должны быть зарезервированы для алгоритма).

Половина ответа уже в вопросе. Используйте hashmap. Если число попадает дважды, используйте разницу индексов, обновляйте лучший результат до сих пор и удаляйте этот номер из хэш-карты на свободное место. Чтобы сделать это O (1), просто повторно используйте исходный массив. Преобразуйте массив в hashmap на месте.

Перед тем, как повернуть элемент массива в ячейку hashmap, запомните его значение и позицию. После этого его можно безопасно перезаписать. Затем используйте это значение, чтобы вычислить новую позицию в хэш-карте и перезаписать ее. Элементы перетасовываются таким образом, пока не будет найдена пустая ячейка. Чтобы продолжить, выберите любой элемент, который еще не переупорядочен. Когда все переупорядочено, каждая пара int определенно попадает дважды, здесь у нас есть пустой хэш файл и обновленное лучшее значение результата.

Один зарезервированный бит используется при преобразовании элементов массива в ячейки hashmap. Сначала он очищается. Когда значение переупорядочено в ячейку hashmap, этот бит устанавливается. Если этот бит не установлен для перезаписанного элемента, этот элемент просто обрабатывается следующим образом. Если этот бит установлен для перезаписываемого элемента, здесь возникает конфликт, выберите первый неиспользуемый элемент (с этим битом не установлен) и перезапишите его.

Более двух зарезервированных битов используются для связывания противоречивых значений. Они кодируют позиции, где цепочка запускается/заканчивается/продолжается. (Возможно, будет возможно оптимизировать этот алгоритм, так что потребуется только 2 зарезервированных бита...)

Ячейка hashmap должна содержать эти 3 зарезервированных бита, индекс исходного значения и некоторую информацию, чтобы однозначно идентифицировать этот элемент. Чтобы сделать это возможным, хеш-функция должна быть обратимой, так что часть значения может быть восстановлена с учетом ее положения в таблице. В простейшем случае хэш-функция - это только ceil(log(n)) младшие значащие биты. Значение в таблице состоит из трех полей:

3 зарезервированные биты
32 - 3 - (ceil(log(n))) старшие биты от исходного значения
ceil(log(n)) бит для позиции элемента в исходном массиве

Сложность по времени - O (n) только в среднем; наихудшей сложностью является O (n ^ 2).

Другим вариантом этого алгоритма является преобразование массива в hashmap последовательно: на каждом шаге m, имеющем 2^m первые элементы массива, преобразованные в hashmap. Некоторые массивы с постоянным размером могут чередоваться с hashmap для повышения производительности, когда m является низким. Когда m высокий, должно быть достаточно int пар, которые уже обработаны и больше не нуждаются в пространстве.

Ответ 4

В O (n) времени и O (1) не может быть сделано это.