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) 矩阵，将数组前半部分的所有元素放置到偶数位置，其他元素放置到奇数位置。这个问题解释了如何进行这种转置（实际上，那里描述的算法应该反向应用）。

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

在 O( N ² ) 时间内排序是微不足道的。插入排序或冒泡排序会做到这一点。

O( N log N ) 时间更复杂。使用稳定的就地合并排序，如this answer中所述。这个答案提供了一对链接，描述了可以用来组成 O( N ) 算法的想法，该算法比稳定的就地合并排序更简单，但仍然相当复杂，所以我只给出它的草图。

---

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

---

1. 临时存储部分数组

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

要准备M个元素用于临时存储，请扫描数组的前M个元素并确定在此范围内代表最少的元素类型。例如，让它成为“数字”。将数字打包成一个大小为M /2 的组。为此，迭代地交换字母和数字块，如下例所示：

ddaaaddddadddaaaaad
aaaDDddddadddaaaaad
aaaaDDDDDDdddaaaaad
aaaaaaaaaDDDDDDDDDd

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

1. 反转数字块
2. 反转数字块
3. 将两个块反转在一起

例子：

123abcd
321abcd
321dcba
abcd123

将数字打包成一组大小为M /2 需要移动最多 ( M /2) ^{2 个}数字和最多N /2 个字母，因此可以在 O( N ) 时间内完成。

准确地说，是 O( N log ² U ) 时间，对 ASCII 字符进行排序是可以的，但是如果我们需要对其他类型的值进行排序，则太大了（U是值集的大小）。为了将运行时间提高到 O( N * log U * log log U )，从大小为 2 * K的较小临时存储开始，使用它对 log U范围进行排序，然后将这些范围与 log 中的块交换过程成对合并记录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矩阵，而是两个 2 x J 矩阵，由两个子阵列组成，用算法转置，在链接答案之一中提到）。

这个过程以及整个算法需要 O( N ) 时间。

---

第二种算法。

由于 ASCII 只包含 10 个数字和 52 个字母，我们可以通过以下方式显着简化算法：

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

---

第三算法。

解决此问题的其他方法是将所有字母排序到数组的开头，将所有数字排序到末尾，并使用（一些修改）就地稳定基数排序，如本 pdf中所述。排序后，应用前面提到的转置算法。

这里最棘手的是这个基数排序算法的压缩部分。我们不能从每个值中保存一位。相反，我们应该使用算术编码。

Answer 2

我相信这个问题可以看作是两个序列的稳定就地合并。鉴于此，它应该可以在 O(n) 时间和 O(1) 空间内求解，因为可以在 O(n) 时间内完成等大小数组的稳定就地合并（例如，参见http:// comjnl.oxfordjournals.org/content/38/8/681.abstract）。

但是，执行此操作的算法完全不是简单的实现（并且可以为 CS 本科生制作一个体面的小型研究项目）。

在任何情况下，在 O(n log n) 时间和 O(1) 时间内对数组进行稳定排序绝对是可能的（参见，例如http://www.springerlink.com/content/d7348168624070v7/?MUD=MP），其中为算法的复杂性设置了一个上限。

Answer 3

这是一个 O(N²) 的实现

def is_digit(s):
    if isinstance(s, str):
        return False
    return True

def interleave(items):
    if len(items) < 2:
        return

    loc = 1
    max_loc = len(items)
    prev_is_digit = is_digit(items[0])

    while loc < max_loc:
        if is_digit(items[loc]) == prev_is_digit:
            # proceed through the list looking for the next item that has the 
            # opposite type
            for i in xrange(loc + 1, max_loc + 1):
                if is_digit(items[i]) != prev_is_digit:
                    # found the opposite type
                    val = items[i]

                    # once the item is found, shift everything up to the item
                    # over by one
                    for j in xrange(i, loc, -1):
                        items[j] = items[j - 1]

                    # move the item to It's new place
                    items[loc] = val
                    break
            loc += 2
        else:
            # invert the type we are looking for
            prev_is_digit = not prev_is_digit
            loc += 1


items = ["a","b",2,"c",3,"d",4,1]
interleave(items)
print items

Answer 4

另一个更简单的就地 O(n2) 解决方案如下：1）使用 2 个 ptrs：src 和 dest 2）你想找到第一个非数字字符并将其放在 dest 位置 3）如果 dest 处的字符已经是非数字，然后查找第一个数字并将其与 dest+1 loc 交换

public static void permute_alt(char arr[]) {
    int src=0, dest=0;

    while (dest < arr.length) {
        if (isChar(arr[dest])) {   //We have a non-digit at dest idx .Now lets look for
                                       // digit and put it in dest+1 place
            dest++;
            src=dest;
            while (!Character.isDigit(arr[src])) {
                src++;
            }
            swap(arr, src, dest);
            dest++;
        } else {
            src=dest;
            while (!isChar(arr[src])) {
                src++;
            }
            swap(arr, src, dest);
            dest++;

        }
    }

}

src ptr 重置为 dest+1 或 dest 以进行下一次迭代。