英文:
Java ArrayList's merge function complexity
问题
我不得不编写一个函数，用于合并两个给定的已排序（从最小到最大）的整数ArrayList。合并必须在第一个ArrayList中进行（在我们的情况下是列表a），并且我们必须保持排序顺序（从最小到最大）。
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)) {
a.add(currentIndexListA, b.get(currentIndexListB));
currentIndexListB++;
}
currentIndexListA++;
}
}
所以，我对算法的复杂性有些困惑。任务是使用O(N)的复杂性制作最大效率的算法。我认为这是O(N)的复杂性，但面试官回答说这段代码效率低下。这正确吗？
英文:
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<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)) {
a.add(currentIndexListA, 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
得分: 2
您在代码中使用了 ArrayList.add 函数来按索引插入数据，这会在指定位置插入数据并移动其他元素。ArrayList 类中的 add 函数使用 System.arraycopy 来移动元素，而 System.arraycopy 使用本机实现，具有 O(N) 复杂度，其中 N 是移动的元素数量。因此，您的算法效率不高。
正如 @SomeDude 所建议的，更好的方法是使用新的 ArrayList，如下所示：
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) {
c.add(aElem);
ixa++;
}else {
c.add(bElem);
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<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) {
c.add(aElem);
ixa++;
}else {
c.add(bElem);
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);
}
}
通过集体智慧和协作来改善编程学习和解决问题的方式。致力于成为全球开发者共同参与的知识库，让每个人都能够通过互相帮助和分享经验来进步。
评论