java - Given an array [a1b2c3d4] convert to [abcd1234]

Question

Constraints :

1. O(1) space
2. O(n) Time

It is not a homework question just a interesting question I came across.

Here are some solutions I could think of but nothing that does it in given constraints.

Method 1

*With O(n) memory *

• Divide the array in two parts recursively. ( keep dividing till the size <=2 for each sub problem )
• Sort each sub problem with array first and numbers at end.
• Merge the sub problem arrays

Method 2

In O(n log n) time

• Sort the array based Lexicographical order it becomes 1234abcd
• Reverse both halves of array 4321dcba
• Reverse the whole string abcd1234

Method 3

If range of numbers was defined

Also if the case was that numbers are in a specific range then I can initialize a int say track= 0; And set the appropriate bit when I come across a number in array eg (1 << a[2] ) . 1. Swap alphabets to first half of array 2. Mark numbers in track variable 3. later use track to fill in second half of array.

Method 4 We can use Method 3 with HashMap if we want to remove the constraint of range of integers but then it will need more memory.

Cannot think of a better way to solve the generic problem in O(1) time and O(n) space.

Generic Problem here refers to:

Given a sequence x1y1x2y2x3y3....xnyn where x1 , x2 are alphabets x1 < x2 <.... < xn and y1y2...yn are integers . y1 < y2 <.... < yn Arrange the output as x1x2...xny1y2...yn

Any suggestions ?

Answer 1

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

这称为列表的卷积。本质上，您必须将一对列表转换(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。

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

Answer 2

@coder 提到的循环领导算法有效。只需确保将数组拆分为 (3^n + 1) 的大小。应用循环领导算法，然后合并它们。

Answer 3

解决方案：

1. 第一个（索引 0）和最后一个（索引 n-1）不动。
2. 总移动次数为 (n - 2)

3. 源中的偶数元素是字母。他们进入上半场。

   target = j/2 // n 是偶数

4. 源中的奇数元素是数字，它们移动到后半部分。

   目标 = n/2 + 楼层(j/2)

5. 从第一个元素开始，将其移动到其目标位置。

6. 将您在目标位置找到的内容移动到其目的地，依此类推，直到形成一个循环。注 1：有时，循环不包括列表中的所有元素，因此，继续 j + 2 注 2：有时，在一个循环结束时，会得到所需的解决方案，但如果我们继续，数组会再次被打乱。要解决此问题，请计算发生的移动次数，并在达到 n - 2 时停止。

您可以尝试运行代码，在此处克隆和编辑 Online Java Compiler 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

}

Answer 4

这是我在 O(n) 中的算法。

无效的cycle_leader（int *arr，int n）{

for (int i = 1; i < n / 2; i+= 2)
{
    int j = i;
    int save;
    int tmp = arr[i];

    do{
        if (j & 1) //odd index element
            j = n / 2 + j / 2;
        else
            j = j / 2;

        save = arr[j];
        arr[j] = tmp;
        tmp = save;
    } while(j != i);
}

}