blocks|key|1236449|text|为了简单起见，假设数组的长度相同，并且是int数组。|type|unstyled|depth|inlineStyleRanges|offset|length|style|CODE|entityRanges|data|1236450|int[]+merge(int[]+a,+int[]+b)
{
++++assert+(a.length+==+b.length);

++++int[]+result+=+new+int[a.length+%2B+b.length];

++++for+(int+i=0;+i<a.length;+i%2B%2B)
++++{
++++++++result[i*2]+=+a[i];
++++++++result[i*2%2B1]+=+b[i];
++++}

++++return+result;
}|code-block|syntax|javascript|1236451|entityMap^0|K|3|0|0^^$0|@$1|2|3|4|5|6|7|M|8|@$9|N|A|O|B|C]]|D|@]|E|$]]|$1|F|3|G|5|H|7|P|8|@]|D|@]|E|$I|J]]|$1|K|3|-4|5|6|7|Q|8|@]|D|@]|E|$]]]|L|$]]

For simplicity, assume that the arrays are the same length, and are <code>int</code> arrays.

<pre><code>int[] merge(int[] a, int[] b)
{
 assert (a.length == b.length);

 int[] result = new int[a.length + b.length];

 for (int i=0; i&lt;a.length; i++)
 {
 result[i*2] = a[i];
 result[i*2+1] = b[i];
 }

 return result;
}
</code></pre>

blocks|key|1236476|text|我相信马特答案中的国防部(%25)操作是不正确的。在相同的假设(数组的长度相同)下，我将提出以下解决方案：|type|unstyled|depth|inlineStyleRanges|entityRanges|data|1236477|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%2B%2B)
++++{
++++++++result[i+<<+1]+=+a[i];
++++++++result[(i+<<+1)+%2B+1]+=+b[i];
++++}

++++return+result;
}|code-block|syntax|javascript|1236478|我对它进行了测试(非常简短)，它看起来很有效，但当然不会尝试处理错误条件，例如空参数或大小不匹配的输入数组。|1236479|entityMap^0|0|0|0^^$0|@$1|2|3|4|5|6|7|K|8|@]|9|@]|A|$]]|$1|B|3|C|5|D|7|L|8|@]|9|@]|A|$E|F]]|$1|G|3|H|5|6|7|M|8|@]|9|@]|A|$]]|$1|I|3|-4|5|6|7|N|8|@]|9|@]|A|$]]]|J|$]]

I believe the mod (%) operations in Matt's answer are incorrect. Under the same assumption (that the arrays are the same length), I'd propose the following solution instead:

<pre><code>static int[] merge(final int[] a, final int[] b)
{
 final int[] result = new int[a.length * 2];

 for (int i=0; i &lt; a.length; i++)
 {
 result[i &lt;&lt; 1] = a[i];
 result[(i &lt;&lt; 1) + 1] = b[i];
 }

 return result;
}
</code></pre>

I tested (very briefly), and it appears to work, but of course makes no attempt to handle error conditions such as null arguments or input arrays mismatched in size.

blocks|key|2792542|text|我认为，对于数组或基于数组的列表，对于给定的约束(O(n)时间和O(1)空间，即没有额外的空间)，这是不可行的。(当然，我们不能简单地创建一个新的List对象，委托给原始的List对象。)|type|unstyled|depth|inlineStyleRanges|offset|length|style|CODE|entityRanges|data|2792543|如果您有两个链接列表，这是可行的--如果我们假设垃圾收集器足够快，即从一个列表中删除一个元素并将其添加到另一个列表并不违反空间限制。|2792544|public+<X>+void+interleaveLists(List<X>+first,+List<X>+second)
{
++++ListIterator<X>+firstIt+=+first.listIterator();
++++ListIterator<X>+secondIt+=+second.listIterator();
++++while(secondIt.hasNext())+{
++++++++fistIt.next();
++++++++firstIt.add(secondIt.next());
++++++++secondIt.remove();
++++}
}|code-block|syntax|javascript|2792545|此方法适用于任意一对列表，但对于链接列表仅为O(n)。|2792546|对于可以修改指针的自定义链接列表，我们不必依赖垃圾收集器，只需更改节点即可。这里有一个单链列表：|2792547|public+void+interleaveLinkedLists(Node<X>+firstList,+Node<X>+secondList)+{
++++while(secondList+!=+null)+{
++++++++Node<X>+nextFirst+=+firstList.next;
++++++++Node<X>+nextSecond+=+secondList.next;
++++++++firstList.next+=+secondList;
++++++++secondList.next+=+nextFirst;
++++++++firstList+=+nextFirst;
++++++++secondList+=+nextSecond;
++++}
}|2792548|对于一个双链接的列表，我们还必须修改prev-指针。|2792549|在这里，第一段中提到的包装变体：|2792550|public+List<X>+interleaveLists(final+List<X>+first,+final+List<X>+second)
{
+++if+(first.size()+!=+second.size())
++++++throw+new+IllegalArgumentException();
+++return+new+AbstractList<X>()+{
++++++public+int+size()+{
+++++++++return+2+*+first.size();
++++++}
++++++public+X+get(int+index)+{
+++++++++return+index+%25+2+==+0+?+first.get(index+/+2)+:+second.get(index+/+2);
++++++}
++++++//+if+necessary,+add+a+similar+set()+method.++add/remove+are+not+sensible+here.
+++};
}|2792551|这也是时间上的O(1)。|2792552|entityMap^0|P|4|W|4|0|0|0|0|0|0|0|0|0|7|4|0^^$0|@$1|2|3|4|5|6|7|12|8|@$9|13|A|14|B|C]|$9|15|A|16|B|C]]|D|@]|E|$]]|$1|F|3|G|5|6|7|17|8|@]|D|@]|E|$]]|$1|H|3|I|5|J|7|18|8|@]|D|@]|E|$K|L]]|$1|M|3|N|5|6|7|19|8|@]|D|@]|E|$]]|$1|O|3|P|5|6|7|1A|8|@]|D|@]|E|$]]|$1|Q|3|R|5|J|7|1B|8|@]|D|@]|E|$K|L]]|$1|S|3|T|5|6|7|1C|8|@]|D|@]|E|$]]|$1|U|3|V|5|6|7|1D|8|@]|D|@]|E|$]]|$1|W|3|X|5|J|7|1E|8|@]|D|@]|E|$K|L]]|$1|Y|3|Z|5|6|7|1F|8|@$9|1G|A|1H|B|C]]|D|@]|E|$]]|$1|10|3|-4|5|6|7|1I|8|@]|D|@]|E|$]]]|11|$]]

I think this is not doable with your given constraints (<code>O(n)</code> time and <code>O(1)</code> space, i.e. no additional space) for an array or array-based list. (Assuming of course, that we can't simply create a new List object delegating to the original ones.)

If you have two linked lists, this is doable - if we assume the garbage collector is fast enough, i.e. deleting an element from one list and adding it to another list does not violate the space limitation.

<pre><code>public &lt;X&gt; void interleaveLists(List&lt;X&gt; first, List&lt;X&gt; second)
{
 ListIterator&lt;X&gt; firstIt = first.listIterator();
 ListIterator&lt;X&gt; secondIt = second.listIterator();
 while(secondIt.hasNext()) {
 fistIt.next();
 firstIt.add(secondIt.next());
 secondIt.remove();
 }
}
</code></pre>

This method works for any pair of lists, but is only O(n) for linked lists.

For a custom linked list where we can modify the pointers, we don't have to rely on the garbage collector, we would simply change the nodes. Here for a singly-linked list:

<pre><code>public void interleaveLinkedLists(Node&lt;X&gt; firstList, Node&lt;X&gt; secondList) {
 while(secondList != null) {
 Node&lt;X&gt; nextFirst = firstList.next;
 Node&lt;X&gt; nextSecond = secondList.next;
 firstList.next = secondList;
 secondList.next = nextFirst;
 firstList = nextFirst;
 secondList = nextSecond;
 }
}
</code></pre>

For a doubly-linked list, we would also have to adapt the prev-pointers.

Here the wrapping variant mentioned in the first paragraph:

<pre><code>public List&lt;X&gt; interleaveLists(final List&lt;X&gt; first, final List&lt;X&gt; second)
{
 if (first.size() != second.size())
 throw new IllegalArgumentException();
 return new AbstractList&lt;X&gt;() {
 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.
 };
}
</code></pre>

This is actually <code>O(1)</code> in time, too.

blocks|key|2433367|text|我已经完成了一个小的解决方案，假设您正在讨论使用ArrayList+(请参阅我对这个问题的评论)。根据这里的一些答复，我可能过于简单化了这个问题，但无论如何，我还是要这样做。|type|unstyled|depth|inlineStyleRanges|offset|length|style|CODE|entityRanges|data|2433368|下面的示例将a和b都作为ArrayList<Integer>类型，并在a之后插入b，在a1后插入b1等。当然，这个片段天真地假定a和b的大小与您的编辑版本1.0相同。它也不会像您的编辑v2.0那样创建新的ArrayList。|2433369|//a+and+b+are+of+type+ArrayList<Integer>
for+(int+i+=+a.size();+i+>+0;+i--)
{
++++a.add(i,+b.get(i+-+1));
}|code-block|syntax|javascript|2433370|无论发生什么，如果您正在组合ArrayLists，您将有两倍的大小。|2433371|entityMap^0|O|9|0|C|I|2U|9|0|0|0^^$0|@$1|2|3|4|5|6|7|Q|8|@$9|R|A|S|B|C]]|D|@]|E|$]]|$1|F|3|G|5|6|7|T|8|@$9|U|A|V|B|C]|$9|W|A|X|B|C]]|D|@]|E|$]]|$1|H|3|I|5|J|7|Y|8|@]|D|@]|E|$K|L]]|$1|M|3|N|5|6|7|Z|8|@]|D|@]|E|$]]|$1|O|3|-4|5|6|7|10|8|@]|D|@]|E|$]]]|P|$]]

I've done up a small solution going on the assumption that you are talking about using the <code>ArrayList</code> (see my comment on the question). I may be oversimplifying the problem based on some of the responses here, but here goes anyway.

The below example takes a and b both of type <code>ArrayList&lt;Integer&gt;</code> and interleaves them by inserting b[0] after a[0], b[1] after a[1] etc. This snippet of course naively assumes that a and b are of the same size as per your Edit v1.0. It also does not create a new <code>ArrayList</code> as per your Edit v2.0.

<pre><code>//a and b are of type ArrayList&lt;Integer&gt;
for (int i = a.size(); i &gt; 0; i--)
{
 a.add(i, b.get(i - 1));
}
</code></pre>

No matter what happens if you are combining the ArrayLists you're going to have twice the size.

blocks|key|1236652|text|列表不必大小相同：|type|unstyled|depth|inlineStyleRanges|entityRanges|data|1236653|public+class+InterleaveTwoLists<X>+{

++++public+List<X>+interleaveLists(final+List<X>+first,+final+List<X>+second)+{

++++++++return+new+AbstractList<X>()+{
++++++++++++private+int+minSize;
++++++++++++private+int+combinedMinSize;
++++++++++++private+int+size;
++++++++++++private+List<X>largerList;
++++++++++++{{
++++++++++++++++minSize+=+Math.min(first.size(),+second.size());
++++++++++++++++combinedMinSize+=+minSize*2;
++++++++++++++++size+=+first.size()+%2B+second.size();
++++++++++++++++largerList+=+first.size()+>+minSize+?+first+:+second;
++++++++++++}}

++++++++++++public+int+size()+{
++++++++++++++++return+size;
++++++++++++}

++++++++++++public+X+get(int+index)+{
++++++++++++++++if+(index+<+combinedMinSize)+{
++++++++++++++++++++return+index+%25+2+==+0+
++++++++++++++++++++++++?+first.get(index+/+2)+
++++++++++++++++++++++++:+second.get(index+/+2);
++++++++++++++++}
++++++++++++++++else+{+
++++++++++++++++++++return+largerList.get(index-minSize);
++++++++++++++++}
++++++++++++}
++++++++};
++++}
}|code-block|syntax|javascript|1236654|要测试这一点：|1236655|public+class+InterleaveTwoListsTest+{

++++private+static+final+Logger+log+=+
++++++++LoggerFactory.getLogger(InterleaveTwoListsTest.class);

++++List<String>+first+=+new+ArrayList<String>()+{
++++{+
++++++++add("one");+add("three");+add("five");+
++++++++add("seven");+add("eight");+add("nine");
++++}};

++++List<String>+second+=+new+ArrayList<String>()+{
++++{+
++++++++add("two");+add("four");+add("six");+
++++}};


++++private+InterleaveTwoLists<String>+interleaveTwoLists;

++++@Before
++++public+void+setUp()+throws+Exception+{
++++++++interleaveTwoLists+=+new+InterleaveTwoLists<>();
++++}

++++@Test
++++public+void+test()+{
++++++++List<String>+combinedList+=+interleaveTwoLists.interleaveLists(first,+second);
++++++++for(+int+i+=+0;+i+<+first.size()+%2B+second.size();+i%2B%2B)+{+
++++++++++++log.debug("{}:+{}",+i,+combinedList.get(i));
++++++++}
++++}
}|1236656|entityMap^0|0|0|0|0^^$0|@$1|2|3|4|5|6|7|M|8|@]|9|@]|A|$]]|$1|B|3|C|5|D|7|N|8|@]|9|@]|A|$E|F]]|$1|G|3|H|5|6|7|O|8|@]|9|@]|A|$]]|$1|I|3|J|5|D|7|P|8|@]|9|@]|A|$E|F]]|$1|K|3|-4|5|6|7|Q|8|@]|9|@]|A|$]]]|L|$]]

The lists don't have to be the same size: 

<pre><code>public class InterleaveTwoLists&lt;X&gt; {

 public List&lt;X&gt; interleaveLists(final List&lt;X&gt; first, final List&lt;X&gt; second) {

 return new AbstractList&lt;X&gt;() {
 private int minSize;
 private int combinedMinSize;
 private int size;
 private List&lt;X&gt;largerList;
 {{
 minSize = Math.min(first.size(), second.size());
 combinedMinSize = minSize*2;
 size = first.size() + second.size();
 largerList = first.size() &gt; minSize ? first : second;
 }}

 public int size() {
 return size;
 }

 public X get(int index) {
 if (index &lt; combinedMinSize) {
 return index % 2 == 0 
 ? first.get(index / 2) 
 : second.get(index / 2);
 }
 else { 
 return largerList.get(index-minSize);
 }
 }
 };
 }
}
</code></pre>

To test this: 

<pre><code>public class InterleaveTwoListsTest {

 private static final Logger log = 
 LoggerFactory.getLogger(InterleaveTwoListsTest.class);

 List&lt;String&gt; first = new ArrayList&lt;String&gt;() {
 { 
 add("one"); add("three"); add("five"); 
 add("seven"); add("eight"); add("nine");
 }};

 List&lt;String&gt; second = new ArrayList&lt;String&gt;() {
 { 
 add("two"); add("four"); add("six"); 
 }};


 private InterleaveTwoLists&lt;String&gt; interleaveTwoLists;

 @Before
 public void setUp() throws Exception {
 interleaveTwoLists = new InterleaveTwoLists&lt;&gt;();
 }

 @Test
 public void test() {
 List&lt;String&gt; combinedList = interleaveTwoLists.interleaveLists(first, second);
 for( int i = 0; i &lt; first.size() + second.size(); i++) { 
 log.debug("{}: {}", i, combinedList.get(i));
 }
 }
}
</code></pre>

blocks|key|2792733|text|与此同时，兰博达被介绍了。|type|unstyled|depth|inlineStyleRanges|entityRanges|data|2792734|O(n)时间复杂度|2792735|O(1)空间复杂度|2792736|int[]+merge(int[]+a,+int[]+b)+{
++++return(+IntStream.range(+0,+a.length+).flatMap(
++++++++n+->+IntStream.of(+a[n],+b[n]+)+).toArray()+);
}|code-block|syntax|javascript|2792737|entityMap^0|0|0|0|0^^$0|@$1|2|3|4|5|6|7|M|8|@]|9|@]|A|$]]|$1|B|3|C|5|6|7|N|8|@]|9|@]|A|$]]|$1|D|3|E|5|6|7|O|8|@]|9|@]|A|$]]|$1|F|3|G|5|H|7|P|8|@]|9|@]|A|$I|J]]|$1|K|3|-4|5|6|7|Q|8|@]|9|@]|A|$]]]|L|$]]

in the meantime lambda was introduced 
O(n) time complexity 
O(1) space complexity
<pre><code>int[] merge(int[] a, int[] b) {
 return( IntStream.range( 0, a.length ).flatMap(
 n -&gt; IntStream.of( a[n], b[n] ) ).toArray() );
}
</code></pre>

I found <a href="https://stackoverflow.com/questions/1860490/interleaving-multiple-arrays-into-a-single-array">similar</a> question about interleaving two arraylists into one, but its in PHP. I was asked this question in interview as well but could'nt solve it, came back to SO to look if it was addressed already, but i could only find this <a href="http://arxiv.org/abs/0805.1598" rel="nofollow noreferrer">paper</a>

So any pointers to pseudo code or method definition ?

Big(O) restrictions : O(n) - time cost and O(1) - space cost

<blockquote>
 Example: 
 a[]= a1, a2, ..., an 
 b[]= b1, b2, ..., bn 
 Rearrange the arraylist to a1, b1, a2, b2, ..., an, bn
</blockquote>

Editv1.0 : Arraylists a[] and b[] are of same size 

Editv2.0 : What if the question is extended to rearrange in one of given two arrays, but not create a new array ?

Java: Interleaving multiple arrays into a single array

翻译质量差，导致语言生硬或混乱。

没有提供实际的解决方法或示例。

解答不清晰，无法理解或解决问题。

页面排版不美观，阅读体验差。

文章

问答

视频

学习中心

腾讯云实验室

直播

竞赛

腾讯云代码分析专区

腾讯iOA零信任安全管理系统专区

腾讯云架构师技术同盟交流圈

腾讯云数据库专区

腾讯云顾问专区

腾讯云原生专区

腾讯混元专区

腾讯云TCE专区

腾讯云Lighthouse专区

腾讯云HAI专区

腾讯云Edgeone专区

腾讯云存储专区

腾讯云智能专区

腾讯轻联专区 

腾讯云开发专区

TAPD专区

腾讯轻量云游戏服专区

腾讯云最具价值专家

腾讯云架构师技术同盟

腾讯云创作之星

腾讯云开发者先锋

腾讯云代码助手

云原生构建

TAPD 敏捷项目管理

Cloud Studio

SDK中心

API中心

命令行工具

涵盖代码开发、场景应用、自动测试全流程，助你从零构建专属AI助手

一站式MCP教程库，解锁AI应用新玩法

我发现了关于将两个数组列表交织成一个的问题，但它是在PHP中的。我也在面试中被问到这个问题，但没能解决，所以回来看看是否已经被解决了，但我只能找到这个那么指向伪代码或方法定义的指针呢？大(O)限制: O(n) -时间成本和O(1) -空间成本示例：a[]= a1，a2，.b[]= b1，b2，.将数组重新排列为a1，b...

问Java:将多个数组交织成一个数组
EN

社区

活动

圈层

关于

腾讯云开发者

热门产品

热门推荐

更多推荐

问Java:将多个数组交织成一个数组EN

社区

活动

圈层

关于

腾讯云开发者

热门产品

热门推荐

更多推荐

问Java:将多个数组交织成一个数组
EN