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

Ответ 1

Да, возможно, с O (n ^ 2) алгоритмом времени:

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

Затем сделайте то же самое, начиная с индекса 1, 2,... Но прежде чем делать какие-либо изменения, выполняйте алгоритм лидера цикла без каких-либо изменений, начиная с этого индекса. Если этот цикл содержит индекс ниже начального индекса, просто пропустите его.

Или этот O (n ^ 3) алгоритм времени:

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

Затем сделайте то же самое, начиная с индекса 1, 2,... Но прежде чем делать какие-либо изменения, выполните алгоритм лидера цикла без каких-либо изменений, начиная со всех предыдущих индексов. Если текущий индекс присутствует в любом предыдущем цикле, просто пропустите его.

Я написал (немного оптимизирован) реализация алгоритма O (n ^ 2) в С++ 11, чтобы определить, сколько дополнительных запросов требуется для каждого элемента на если случайная перестановка инвертирована. Вот результаты:

size accesses
2^10 2.76172
2^12 4.77271
2^14 6.36212
2^16 7.10641
2^18 9.05811
2^20 10.3053
2^22 11.6851
2^24 12.6975
2^26 14.6125
2^28 16.0617

Пока размер растет экспоненциально, количество обращений к элементу растет почти линейно, поэтому ожидаемая временная сложность для случайных перестановок - это что-то вроде O (n log n).

Ответ 2

Инвертирование массива A требует от нас найти перестановку B, которая удовлетворяет требованию A[B[i]] == i для всех i.

Чтобы построить обратное на месте, мы должны поменять элементы и индексы, установив A[A[i]] = i для каждого элемента A[i]. Очевидно, что если бы мы просто перешли через A и выполнили вышеупомянутую замену, мы могли бы переопределить предстоящие элементы в A, и наши вычисления потерпят неудачу.

Поэтому мы должны поменять элементы и индексы на циклы A, следуя c = A[c], пока не достигнем нашего начального индекса цикла c = i.

Каждый элемент из A принадлежит одному из таких циклов. Поскольку у нас нет места для хранения, если элемент A[i] уже обработан и должен быть пропущен, мы должны следовать его циклу: если мы достигнем индекса c < i, мы бы знали, что этот элемент является частью ранее обработанный цикл.

Этот алгоритм имеет худшую временную сложность O (n²), среднюю сложность во времени O (n log n) и лучшую Сложная временная сложность O (n).

function invert(array) {
  main:
  for (var i = 0, length = array.length; i < length; ++i) {
    
    // check if this cycle has already been traversed before:
    for (var c = array[i]; c != i; c = array[c]) {
      if (c <= i) continue main;
    }
    
    // Replacing each cycle element with its predecessors index:
    var c_index = i, 
        c = array[i];
    do {
      var tmp = array[c];
      array[c] = c_index; // replace
      c_index = c; // move forward
      c = tmp;
    } while (i != c_index)
      
  }
  return array;
}
  
console.log(invert([3, 1, 0, 2, 4])); // [2, 1, 3, 0, 4]