在恒定空间中交错数组 [英] Interleave array in constant space

问题描述

假设我们有一个数组a1, a2,... , an, b1, b2, ..., bn.

目标是将此数组更改为a1, b1, a2, b2, ..., an, bn 在 O(n) 时间和 O(1) 空间中.换句话说，我们需要一个线性时间算法来就地修改数组，并且不会超过恒定的额外存储量.

如何做到这一点?

解决方案

这是我用笔和纸制定的顺序和笔记.我认为它或变体适用于任何更大的 n.

每行代表一个不同的步骤，() 表示这一步移动的内容，[] 表示从上一步移动的内容.数组本身用作存储，并且需要两个指针(一个用于 L，一个用于 N)来确定下一步要移动的内容.L 的意思是字母线"并且N是数轴"；(移动了什么).

<前>A B C D 1 2 3 4L A B C (D) 1 2 3 4 第一个是 L，最后 N 不需要移动N A B C (3) 1 2 [D] 4L A B (C) 2 1 [3] D 4不适用 B 1 (2) [C] 3 D 4L A (B) 1 [2] C 3 D 4不适用 (1) [B] 2 C 3 D 4A [1] B 2 C 3 D 4 完成，无需移动 A

注意变化的指针跳转"- L 指针总是递减 1(因为它不能被更快地吃掉)，但 N 指针根据它是否替换自己"而跳转(原地，跳下两个)或者如果它交换了一些东西(不跳，所以下一个东西可以开始！).

Suppose we have an array a1, a2,... , an, b1, b2, ..., bn.

The goal is to change this array to a1, b1, a2, b2, ..., an, bn in O(n) time and in O(1) space. In other words, we need a linear-time algorithm to modify the array in place, with no more than a constant amount of extra storage.

How can this be done?

解决方案

This is the sequence and notes I worked out with pen and paper. I think it, or a variation, will hold for any larger n.

Each line represents a different step and () signifies what is being moved this step and [] is what has been moved from last step. The array itself is used as storage and two pointers (one for L and one for N) are required to determine what to move next. L means "letter line" and N is "number line" (what is moved).

   A   B   C   D    1   2   3   4

L  A   B   C  (D)   1   2   3   4  First is L, no need to move last N
N  A   B   C  (3)   1   2  [D]  4
L  A   B  (C)  2    1  [3]  D   4
N  A   B   1  (2)  [C]  3   D   4
L  A  (B)  1  [2]   C   3   D   4
N  A  (1) [B]  2    C   3   D   4
   A  [1]  B   2    C   3   D   4  Done, no need to move A

Note the varying "pointer jumps" - the L pointer always decrements by 1 (as it can not be eaten into faster than that), but the N pointer jumps according to if it "replaced itself" (in spot, jump down two) or if it swapped something in (no jump, so the next something can get its go!).

这篇关于在恒定空间中交错数组的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！