Если массив [a1b2c3d4] преобразован в [abcd1234]

Ограничения:

  • O (1) пространство
  • O (n) Время

Это не вопрос домашней работы, а интересный вопрос, который я встретил.

Вот некоторые решения, о которых я мог думать, но ничего не делает в заданных ограничениях.

Метод 1

* С памятью O (n) *

  • Разделите массив на две части рекурсивно. (продолжайте делить до размера <= 2 для каждой дополнительной проблемы).
  • Сортируйте каждую вспомогательную проблему с первым массивом и номерами в конце.
  • Объединить массивы вспомогательных задач

Метод 2

В O (n log n) время

  • Сортировка массива на основе лексикографического порядка составляет 1234abcd
  • Обратить обе половины массива 4321dcba
  • Обратить всю строку abcd1234

Метод 3

Если был определен диапазон чисел

Также, если дело было в том, что числа находятся в определенном диапазоне, тогда я могу инициализировать int say track = 0; И установите соответствующий бит, когда я сталкиваюсь с числом в массиве например (1 < a [2]). 1. Обмен алфавитами в первую половину массива 2. Отметьте числа в переменной дорожки 3. позже используйте дорожку для заполнения второй половины массива.

Метод 4 Мы можем использовать метод 3 с HashMap, если мы хотим удалить ограничение диапазона целых чисел, но тогда ему потребуется больше памяти.

Невозможно представить лучший способ решить общую проблему в O (1) и O (n) пространстве.

Общая проблема здесь относится к:

Учитывая последовательность x1y1x2y2x3y3.... xnyn       где x1, x2 - алфавиты x1 < x2 < хп       и y1y2... yn - целые числа. y1 < y2 < уп Расположите выход как x1x2... xny1y2... yn

Любые предложения?

Ответы

Ответ 1

Что такое n? Предполагая, что n - размер ввода:

Это называется сверткой списка. По сути, вам нужно преобразовать список пар (a,1),(b,2),(c,3),(d,4) в пару списков (a,b,c,d),(1,2,3,4). Это та же операция, что и транспонирование матрицы.

В любом случае, вы должны думать о структуре как k-мерном массиве, где k = lg n. Свертка массива - это то, что вы получаете, когда вы "перемещаете" значение по индексу i, чтобы индексировать я побитовое вращение. В этом случае мы хотим повернуть индексы вправо 1 бит. Это означает, что свертка представляет собой перестановку с максимальной длиной цикла k. Трюк затем выбирает один индекс из каждого цикла - это всегда будет включать 0 и n-1.

EDIT: На самом деле вы, вероятно, хотите разложить перестановку в произведение транспозиций. Затем все, что вам нужно сделать, это свопы.

Ответ 2

Решение:

  • Сначала (индекс 0) и последний (индекс n-1) не перемещаются.
  • Общее количество ходов (n - 2)

  • Четные элементы в источнике - это алфавиты. Они переходят в первую половину.

    target = j/2//n равно

  • Элементы нечетного числа в источнике - это числа, и они перемещаются во вторую половину.

    target = n/2 + floor (j/2)

  • Начиная с 1-го элемента, переместите его в целевое местоположение.

  • Переместите то, что вы находите в целевом местоположении, в пункт назначения и т.д. пока не сформируется петля. Примечание 1: Иногда цикл не включает в себя все элементы в списке, поэтому, продолжайте с j + 2 Примечание 2: Иногда, в конце одного цикла, желаемое решение будет достигнуто, но если мы продолжим, массив снова будет скремблироваться. Чтобы исправить это, подсчитайте количество движений, которые произошли, и вырежьте, когда он достигнет n-2.

Вы можете попробовать запустить код, клонировать и редактировать здесь Интерактивный Java Compiler IDE

int maxShifts = n - 2; // This is required to fix going around and messing up.
int shifts = 0;

for (int i = 1; i < n && shifts < maxShifts; i+=2) {
  int source = i;
  char itemToMove = array[source];
  do {
    int target;
    if (source % 2 == 0) {
      target = source / 2; // Even index is an alphabet
    } else {
      target = n/2 + source/2; // Odd index is a digit, that goes in the second half
    }
    char tmp = array[target];
    array[target] = itemToMove;
    itemToMove = tmp;

    shifts++;
    source = target;

  } while (i != source /*&& shifts < maxShifts*/); // Full cycle reached

}

Ответ 3

Или вы можете использовать могучий Python и перевести его в java:

a = [1,'a',2,'b',3,'c',4,'d']
a = a[0:len(a):2] + a[1:len(a):2]
print(a) #this will print [1,2,3,4,'a','b','c','d']

Ответ 4

Вот мой алгоритм в O (n).

void cycle_leader (int * arr, int n) {

for (int i = 1; i < n / 2; i+= 2)
{
    int j = i;
    int save;
    int tmp = arr[i];

    do{
        if (j & 1) //odd index element
            j = n / 2 + j / 2;
        else
            j = j / 2;

        save = arr[j];
        arr[j] = tmp;
        tmp = save;
    } while(j != i);
}

}