Подтвердить что ты не робот

Отделите алфавит и цифру так, чтобы их относительный порядок оставался неизменным в O (n) времени и O (1) пространстве

Учитывая массив [a1b7c3d2] преобразовать в [abcd1732] с O(1) пробелом и O(n) время, то есть поместить буквы слева и цифры справа, чтобы их относительный порядок был одинаковым. Я могу придумать алгоритм O(nlogn), но не лучше. Кто-нибудь может помочь?

Ответ 1

AFAIK это невозможно. Это по существу один шаг алгоритма сортировки RADIX. И стабильная сортировка RADIX AFAIK не может быть выполнена на месте.

edit Википедия согласна со мной (для чего это стоит):

http://en.wikipedia.org/wiki/Radix_sort#Stable_MSD_radix_sort_implementations

MSD Radix Sort может быть реализована как стабильный алгоритм, но требует использование буфера памяти того же размера, что и входной массив

Edit2

Если вход всегда находится в парах буквенного номера, тогда решение довольно просто, так как мы всегда знаем, какой символ должен идти где:

for i=0...n/2-1
  tmp=array[i]
  if tmp is a letter 
    continue // nothing to do, we have a letter already!
  index=i
  do
    // we have the wrong think at index! Where is it supposed to be?
    if (index is even) // the wrong thing is a letter
      index=index/2
    else // the wrong thing is a number
      index=n/2+index/2
    // we found where temp should go! Lets put it there!
    // But we keep what was already there and look for its place next iteration
    tmp2=array[index]
    array[index]=tmp
    tmp=tmp2
  while index!=i

Он может выглядеть квадратичным, так как для каждого i мы делаем while, но на самом деле каждый элемент перемещается только один раз, поэтому он линейный.

Ответ 2

Во-первых, это действительно дубликат этого SO-вопроса, просто сказано немного по-другому.

(Так как ваша проблема действительно может считаться стабильной сортировкой 0-1)

К сожалению, я не могу понять алгоритм и не найти простой псевдокод, но если вы хотите, чтобы алгоритм был описан здесь: http://www.diku.dk/~jyrki/Paper/KP1992bJ.pdf