# Java ArrayList的合并函数复杂性

go评论57阅读模式

Java ArrayList's merge function complexity

# 问题

``````void merge(ArrayList<Integer> a, ArrayList<Integer> b) {
int currentIndexListA = 0;
int currentIndexListB = 0;

while (currentIndexListB < b.size()) {
if (currentIndexListA == a.size() || a.get(currentIndexListA) > b.get(currentIndexListB)) {
currentIndexListB++;
}
currentIndexListA++;
}
}
``````

I had to write a function that merges two given sorted (from smallest to largest) ArrayList's of Integer's. Merge must be done in the first ArraList (in our case list a) and we must leave the sorted order(from smallest to largest).

`````` void merge(ArrayList&lt;Integer&gt; a, ArrayList&lt;Integer&gt; b) {
int currentIndexListA = 0;
int currentIndexListB = 0;

while(currentIndexListB &lt; b.size()) {
if(currentIndexListA == a.size() || a.get(currentIndexListA) &gt; b.get(currentIndexListB)) {
currentIndexListB++;
}
currentIndexListA++;
}
}
``````

So, i'm a few confusing about complexity of algorithm. The task was to make the maximum efficiency algorithm with complexity of O(N). And I think that it's O(N) complexity, but the interviewer responded that the code is inefficient. Is it correct ?

# 答案1

``````import java.util.ArrayList;

public class Main
{
static void merge2(ArrayList<Integer> a, ArrayList<Integer> b) {

ArrayList<Integer> c = new ArrayList<Integer>();
int ixa=0, ixb=0;
int limita = a.size();
int limitb = b.size();
int aElem = 0;
int bElem = 0;

while(ixa+ixb < limita+limitb ) {

aElem = Integer.MAX_VALUE;
bElem = Integer.MAX_VALUE;

if(ixa < limita)
aElem = a.get(ixa);

if(ixb < limitb)
bElem = b.get(ixb);

if( aElem <= bElem) {
ixa++;
}else {
ixb++;
}
}

for(Integer aa:c) {
System.out.println(aa);
}

}

public static void main(String []args){
ArrayList<Integer> a = new ArrayList<Integer>(Arrays.asList(1,3,5));
ArrayList<Integer> b = new ArrayList<Integer>(Arrays.asList(2,4,6));

merge2(a,b);

ArrayList<Integer> c = new ArrayList<Integer>(Arrays.asList(1,2,3));
ArrayList<Integer> d = new ArrayList<Integer>(Arrays.asList(5,6,7));

merge2(c,d);
}
}
``````

You used ArrayList.add function by index which insert your data at specified position and shift other elements. `add` function in ArrayList class uses `System.arraycopy` to shift elements and `System.arraycopy` uses native implementation with O(N) which N is the number of shifted elements. So you algorithm is not efficient.

A better way as @SomeDude said is using new ArrayList such as following:

``````import java.util.ArrayList;
public class Main
{
static void merge2(ArrayList&lt;Integer&gt; a, ArrayList&lt;Integer&gt; b) {
ArrayList&lt;Integer&gt; c = new ArrayList&lt;Integer&gt;();
int ixa=0, ixb=0;
int limita = a.size();
int limitb = b.size();
int aElem = 0;
int bElem = 0;
while(ixa+ixb &lt; limita+limitb ) {
aElem = Integer.MAX_VALUE;
bElem = Integer.MAX_VALUE;
if(ixa &lt; limita)
aElem = a.get(ixa);
if(ixb &lt; limitb)
bElem = b.get(ixb);
if( aElem &lt;= bElem) {
ixa++;
}else {
ixb++;
}
}
for(Integer aa:c) {
System.out.println(aa);
}
}
public static void main(String []args){
ArrayList&lt;Integer&gt; a = new ArrayList&lt;Integer&gt;(Arrays.asList(1,3,5));
ArrayList&lt;Integer&gt; b = new ArrayList&lt;Integer&gt;(Arrays.asList(2,4,6));
merge2(a,b);
ArrayList&lt;Integer&gt; c = new ArrayList&lt;Integer&gt;(Arrays.asList(1,2,3));
ArrayList&lt;Integer&gt; d = new ArrayList&lt;Integer&gt;(Arrays.asList(5,6,7));
merge2(c,d);
}
}
``````

• 本文由 发表于 2020年10月7日 03:02:46
• 转载请务必保留本文链接：https://go.coder-hub.com/64232233.html
• algorithm
• big-o
• java

go 83

go 75

go 52

go 87