12

Given an array [a1b7c3d2] convert to [abcd1732] with O(1) space and O(n) time i.e. put the letters on the left and digits on the right such that their relative order is the same. I can think of an O(nlogn) algorithm, but not better. Can somebody please help?

4

2 回答 2

3

AFAIK 它无法完成。这本质上是RADIX 排序算法的一个步骤。AFAIK 稳定的RADIX 排序不能就地完成。

编辑Wikipedia 同意我的观点（因为这是值得的）：

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

于 2013-09-28T21:51:25.703 回答
1

首先，这确实是这个 SO question的副本，只是表述方式有所不同。

（因为你的问题真的可以被认为是稳定的 0-1 排序）

不幸的是，我无法弄清楚算法，也找不到任何简单的伪代码，但如果你想在这里描述算法：http ://www.diku.dk/~jyrki/Paper/KP1992bJ.pdf

于 2013-09-28T21:31:04.157 回答