Java：将多个数组交织到一个数组中

我发现类似的问题关于将两个arraylists交织成一个，但它在PHP中。 我在面试中也被问到了这个问题，但无法解决，回到SO看看是否已经解决了，但我只能找到这篇论文

那么任何指向伪代码或方法定义的指针呢？

大（O）限制：O（n） – 时间成本和O（1） – 空间成本

例：
a [] = a1，a2，…，an
b [] = b1，b2，…，bn
将arraylist重新排列为a1，b1，a2，b2，…，an，bn

Editv1.0 ：Arraylists a []和b []具有相同的大小

Editv2.0 ：如果问题扩展到在给定的两个数组之一中重新排列，但是没有创建新数组怎么办？

Answer 1

为简单起见，假设数组长度相同，并且是int数组。

 int[] merge(int[] a, int[] b) { assert (a.length == b.length); int[] result = new int[a.length + b.length]; for (int i=0; i 

Answer 2

我认为这对于基于数组或基于数组的列表的给定约束（ O(n)时间和O(1)空间，即没有额外空间）是不可行的。 （当然，假设我们不能简单地创建一个委托给原始对象的新List对象。）

如果你有两个链表，这是可行的 – 如果我们假设垃圾收集器足够快，即从一个列表中删除一个元素并将其添加到另一个列表不违反空间限制。

 public  void interleaveLists(List first, List second) { ListIterator firstIt = first.listIterator(); ListIterator secondIt = second.listIterator(); while(secondIt.hasNext()) { fistIt.next(); firstIt.add(secondIt.next()); secondIt.remove(); } } 

此方法适用于任何列表对，但对于链接列表仅为O（n）。

对于我们可以修改指针的自定义链表，我们不必依赖垃圾收集器，我们只需更改节点。 这里是一个单链表：

 public void interleaveLinkedLists(Node firstList, Node secondList) { while(secondList != null) { Node nextFirst = firstList.next; Node nextSecond = secondList.next; firstList.next = secondList; secondList.next = nextFirst; firstList = nextFirst; secondList = nextSecond; } } 

对于双向链表，我们还必须调整prev-pointers。

这里是第一段中提到的包装变体：

 public List interleaveLists(final List first, final List second) { if (first.size() != second.size()) throw new IllegalArgumentException(); return new AbstractList() { public int size() { return 2 * first.size(); } public X get(int index) { return index % 2 == 0 ? first.get(index / 2) : second.get(index / 2); } // if necessary, add a similar set() method. add/remove are not sensible here. }; } 

这实际上也是O(1) 。

Answer 3

我已经做了一个小小的解决方案，假设您正在讨论使用ArrayList （请参阅我对该问题的评论）。 我可能会根据这里的一些回答过度简化问题，但无论如何都要进行。

下面的例子采用a和b两种类型ArrayList并通过在[0]之后插入b [0]来交织它们，在[1]之后插入b [1]等。这个片段当然天真地假定a和b与Edit v1.0的大小相同。 它也不会根据您的Edit v2.0创建新的ArrayList 。

 //a and b are of type ArrayList for (int i = a.size(); i > 0; i--) { a.add(i, b.get(i - 1)); } 

无论你如何组合ArrayLists，你将会有两倍的大小。

Answer 4

我相信Matt的答案中的mod（％）操作是不正确的。 在相同的假设下（数组的长度相同），我建议使用以下解决方案：

 static int[] merge(final int[] a, final int[] b) { final int[] result = new int[a.length * 2]; for (int i=0; i < a.length; i++) { result[i << 1] = a[i]; result[(i << 1) + 1] = b[i]; } return result; } 

我测试（非常简短），它似乎工作，但当然不会尝试处理错误条件，如空参数或输入数组大小不匹配。

Answer 5

列表不必具有相同的大小：

 public class InterleaveTwoLists { public List interleaveLists(final List first, final List second) { return new AbstractList() { private int minSize; private int combinedMinSize; private int size; private ListlargerList; {{ minSize = Math.min(first.size(), second.size()); combinedMinSize = minSize*2; size = first.size() + second.size(); largerList = first.size() > minSize ? first : second; }} public int size() { return size; } public X get(int index) { if (index < combinedMinSize) { return index % 2 == 0 ? first.get(index / 2) : second.get(index / 2); } else { return largerList.get(index-minSize); } } }; } } 

为了测试这个：

 public class InterleaveTwoListsTest { private static final Logger log = LoggerFactory.getLogger(InterleaveTwoListsTest.class); List first = new ArrayList() { { add("one"); add("three"); add("five"); add("seven"); add("eight"); add("nine"); }}; List second = new ArrayList() { { add("two"); add("four"); add("six"); }}; private InterleaveTwoLists interleaveTwoLists; @Before public void setUp() throws Exception { interleaveTwoLists = new InterleaveTwoLists<>(); } @Test public void test() { List combinedList = interleaveTwoLists.interleaveLists(first, second); for( int i = 0; i < first.size() + second.size(); i++) { log.debug("{}: {}", i, combinedList.get(i)); } } }