给定一个数组 [a1b2c3d4] 转换为 [abcd1234]

arrays algorithm java array-algorithms

2022-09-04 04:41:51

约束：

O（1）空间
O（n）时间

这不是一个家庭作业问题，只是我遇到的一个有趣的问题。

以下是我能想到的一些解决方案，但在给定的约束下，没有任何解决方案可以做到这一点。

方法 1

*带 O（n）内存 *

以递归方式将数组分为两部分。（继续除法，直到每个子问题的大小<= 2）
首先使用数组，在末尾对每个子问题进行排序。
合并子问题数组

方法 2

在 O（n log n）时间内

对数组进行排序，字典顺序变为 1234abcd
反转阵列 4321dcba 的两半
反转整个字符串 abcd1234

方法 3

如果定义了数字范围

另外，如果情况是数字在特定范围内，那么我可以初始化一个int say track= 0;当我在数组中遇到一个数字时，设置适当的位，例如（1<<a[2]）。1. 将字母表交换到数组 2 的前半部分。在轨道变量 3 中标记编号。稍后使用轨道填充数组的后半部分。

方法 4如果我们想删除整数范围的约束，我们可以将方法3与HashMap一起使用，但随后它将需要更多的内存。

想不出更好的方法来解决O（1）时间和O（n）空间中的一般问题。

这里的一般问题是指：

给定一个序列 x1y1x2y2x3y3....xnyn 其中 x1， x2 是字母 x1 < x2 <....< xn 和 y1y2...yn 是整数。y1 < y2 <....< yn 将输出排列为 x1x2...xny1y2...yn

有什么建议吗？

答案 1

什么？假设这是输入的大小：nn

这称为列表的卷积。从本质上讲，您必须将对列表转换为对列表。它与矩阵的转置操作相同。(a,1),(b,2),(c,3),(d,4)(a,b,c,d),(1,2,3,4)

无论如何，你必须将结构视为一个k维数组，其中k = lg n。数组的卷积是当您将索引i处的值“移动”到按位旋转的索引i时得到的。在本例中，我们希望将索引向右旋转 1 位。这意味着卷积是最大周期长度为 k 的排列。然后，诀窍是从每个周期中选择一个索引 - 这将始终包括0和n-1。

编辑：实际上，你可能想要的是将排列分解为转置的乘积。然后，您需要做的就是交换。

答案 2

溶液：

第一个（索引 0）和最后一个（索引 n-1）不移动。
总移动次数为（n - 2）
源中的偶数元素是字母。他们进入上半场。

目标 = j/2 // n 是偶数
源中的奇数元素是数字，它们移动到后半部分。

目标 = n/2 + 下限（j/2）
从第 1 个元素开始，将其移动到其目标位置。
将您在目标位置找到的内容移动到其目标位置，依此类推，直到形成循环。注1：有时，循环不包括列表中的所有元素，因此，继续j + 2 注意2：有时，在一个循环结束时，将实现所需的解决方案，但是如果我们继续，数组将再次被打乱。要解决此问题，请计算发生的运动次数，并在达到 n - 2 时进行剪切。

您可以尝试运行代码，在此处克隆和编辑在线Java编译器IDE

int maxShifts = n - 2; // This is required to fix going around and messing up.
int shifts = 0;

for (int i = 1; i < n && shifts < maxShifts; i+=2) {
  int source = i;
  char itemToMove = array[source];
  do {
    int target;
    if (source % 2 == 0) {
      target = source / 2; // Even index is an alphabet
    } else {
      target = n/2 + source/2; // Odd index is a digit, that goes in the second half
    }
    char tmp = array[target];
    array[target] = itemToMove;
    itemToMove = tmp;

    shifts++;
    source = target;

  } while (i != source /*&& shifts < maxShifts*/); // Full cycle reached

}