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

Question

Учитывая массив int, каждый int появляется ровно ДВАЖДЫ в массиве.найти и вернуть int так, чтобы эта пара int имела максимальное расстояние между собой в этом массиве.

например, [2, 1, 1, 3, 2, 3]

2: d = 5-1 = 4;
1: d = 3-2 = 1;
3: d = 6-4 = 2;
return 2

Мои идеи:

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

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

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

Answer 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] ?

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

Answer 2

Нет способа сделать это за время O (n) и пространство O (1).

Answer 3

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

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

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

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

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

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

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

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

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

Answer 4

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

Инкремент 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;