将字母和数字分开,使得它们的相对顺序在O(n)时间和O(1)空间中保持相同

Question

给定一个数组[a1b7c3d2]转换为[abcd1732]具有O(1)空间和O(n)时间,即把左边和数字字母的这种权利,他们的相对顺序是一样的.我可以想到一个O(nlogn)算法,但不是更好.有人可以帮忙吗？

Answer 1

AFAIK 这是不可能完成的。这本质上是RADIX 排序算法的一个步骤。而且据我所知，稳定的RADIX 排序无法就地完成。

编辑维基百科同意我的观点（就其价值而言）：

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

MSD 基数排序可以作为稳定的算法实现，但需要使用与输入数组大小相同的内存缓冲区

编辑2

如果输入始终是字母数字对，那么解决方案非常简单，因为我们总是知道哪个字符应该放在哪里：

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元素，但实际上每个元素只移动一次，因此它是线性的。