arrays - 就地交错字符和数字数组的算法

Question

有一个像[a,b,2,c,3,d,4,1]这样的数组。必须就地将其修改为类似[a,2,b,3,c,4,d,1]的数组。

也就是说，从散布有字母和数字的原始数组开始，修改后的版本应包含相同的元素，以使该数组具有交替的字母和数字，同时保留其原始相对顺序。

通过使用两个指针并将修改后的版本输出到新数组中，可以轻松完成此操作，但是必须在O(N)时间和O(1)空间中就地完成。可能吗？如果可以，怎么办？

Answer 1

O（N）就地算法是可能的。您可以将所有字母排序到数组的开头，将所有数字排序到末尾。然后就地转置2x（N / 2）矩阵，以将所有元素从数组的前半部分放置到偶数位置，将其他元素放置到奇数位置。 This question解释了如何进行此转置（实际上，此处描述的算法应反向应用）。

最棘手的部分是排序。它应该既稳定又就位。

按O（N2）时间排序很简单。插入排序或冒泡排序即可。

O（N log N）时间更加复杂。使用稳定的就地合并排序，如this answer中所述。这个答案给出了一对链接，描述了思想，这些链接可以用来构成O（N）算法，它比稳定的就地合并排序要简单，但是仍然很复杂，因此我只给出一个草图。



将阵列分为两个区域。其中一个将用于临时存储算法其他部分所需的一些数据（由于该区域仍应存储数组元素，因此任何其他信息均按这些元素的顺序进行编码）。其他区域被解释为一个正方形矩阵，在这里应该对元素进行排序，首先是行，然后是列。对两个区域进行排序后，对每个区域应用转置算法，以将字符和数字放置在适当的位置。



1.从阵列的一部分中进行临时存储

数组的大多数元素被组织为大小为K的方阵。K是最大的偶数，因此2 * 8 * K + K2不大于N。临时存储的大小M = N-K2，大约为等于2 * 8 * sqrt（N）。

要准备M个元素以进行临时存储，请扫描阵列的前M个元素，然后确定在此范围内最少代表哪种元素。例如，将其设置为“数字”。将数字打包成一组大小为M / 2的数字。为此，迭代交换字母和数字块，如以下示例所示：

ddaaaddddadddaaaaad
aaaDDddddadddaaaaad
aaaaDDDDDDdddaaaaad
aaaaaaaaaDDDDDDDDDd

当单个组中至少收集了M / 2位数字时停止。块交换过程（也可以称为就地子阵列旋转）可以作为 this answer的第一个算法或如下实现：


倒数位
反向数字块
一起反转两个块


例：

123abcd
321abcd
321dcba
abcd123

将数字打包到大小为M / 2的组中需要最多移动（M / 2）2个数字和最多N / 2个字母，因此可以在O（N）时间内完成。

确切地说，现在是O（N log2 U）时间，可以对ASCII字符进行排序，但是如果我们需要对其他类型的值进行排序，则该时间太大（U是值集的大小）。为了将运行时间缩短到O（N * log U * log log U），请从较小的临时存储区大小2 * K开始，使用它对log U范围进行排序，然后将这些范围与块交换过程成对合并，以成对记录记录U步骤以获取适当大小的临时存储。

在这一点上，我们有M / 2大小的数字块，其后是一个字母块（可能是较大的字母）。使用块交换过程来制作两个大小相等的M / 2块。

为了将数据位存储在临时存储中，我们可以在位置i和i + M / 2处交换元素。如果位置i存储一个字母，而位置i + M / 2存储一个数字，则我们有零位。如果数字排在第一位，则我们有非零位。 8个连续位编码单个字符。这意味着，我们最多可以记住临时存储区中的K个字符。

将位存储在临时存储中的其他替代方法是将其“数量”一半。每个数字可以存储为“ 0” ..“ 9”（表示位0），也可以存储为“ a” ..“ j”（表示位1）。如果可能的字母数至少是数字数的3倍，则我们可以在每个值中存储2位。为了从每个值中压缩4位，我们可以将每2位压缩为一个字节。这给出了M / 4个空闲字节；因此M可以减小为4 *K。



2.对矩阵的行进行排序

从这一点出发，我们应该使用临时存储作为附加内存来重新排列阵列的主要区域。确定在大小为2 * K的子数组中最少表示哪种元素。例如，让它为“数字”。顺序扫描阵列，将数字移动到临时存储区，然后将字母打包成连续的序列。当收集到K个数字时，我们将按顺序排列L个字母，并且L> =K。将最后L％K个字母移到空闲区域的末尾，并用临时存储区中的数字填充剩余的空闲区域。然后继续顺序扫描阵列。

此过程仅复制阵列的每个元素一次或两次，因此需要O（N）时间来完成。最后，将所有字母/数字块对齐，以使矩阵的每一行都包含一种元素。





3.对矩阵的列进行排序

这是先前过程的简化版本。对于每个矩阵列，将数字移动到临时存储并将字母打包到连续的行中，然后将数字从临时存储复制到空闲的行。

此过程还需要O（N）时间才能完成。在最后，数组的主要区域已完全排序。现在对临时存储进行排序（将零写入每个“位”）。



4.转置数组

剩下的唯一步骤是转置阵列的临时存储区和主区域，以使字符和数字位于适当的位置。 （请注意，不是其中的一个链接答案中提到的算法，就是将由两个子阵列组成的两个K x K矩阵而不是K x K矩阵进行转置）。

此过程以及整个算法需要O（N）时间。





第二种算法。

由于ASCII仅包含10位数字和52个字母，因此我们可以通过以下方式大大简化算法：


使用BASE64编码压缩值的最后1/3，这将提供N / 12字节的可用空间（用作临时存储）。
使用此空间作为临时存储对值的前1/3进行排序：确定大小为N / 6的子数组中最少表示的元素类型；例如，使其为“数字”；顺序扫描阵列，将数字移动到临时存储区，并将字母包装成连续序列；然后将临时存储复制到空闲空间；对接下来的N / 6个元素重复此操作。
解压缩值的最后1/3，解压缩值的前1/3。
排序最后2/3个值（将N / 6个元素排序4次）。
解压缩值的前1/3。
此时，我们有12组字符（大小可变）。使用块交换过程在这些组之间移动这些组，并以适当的顺序（字母，数字等）制作12个大小相等的组。
转置6对字符组。实际上，这里可以使用简单的换位算法。对所有未标记元素（位7为零）应用循环前导算法，并在移动元素时将其位7设置为1。完成后，清除所有标记。




第三算法。

解决此问题的另一种方法是，将所有字母排序到数组的开头，将所有数字排序到末尾，并用 this pdf中描述的就地稳定基数排序（对它进行一些修改）。排序后，应用前面提到的转置算法。

这里最棘手的事情是此基数排序算法的压缩部分。我们无法从每个值中节省一位。相反，我们应该使用算术编码。