如何对2个未排序的列表进行排序并创建排序列表

Question

我得到了两个未排序的数组列表，它们只有一个排序列表。我不被允许对前两个列表进行排序。

我只是将这两个列表都转储到优先级队列中，然后取出值并将其放入第三个列表中。喜欢

public static void sortList() {
ArrayList<Integer> l1 = new ArrayList<>();
l1.add(10);
l1.add(11);
l1.add(8);
l1.add(15);
l1.add(2);
ArrayList<Integer> l2 = new ArrayList<>();
l2.add(11);
l2.add(2);
l2.add(15);
l2.add(18);
PriorityQueue<Integer> queue = new PriorityQueue<>();
for (int i = 0; i < l1.size(); i++) {
queue.add(l1.get(i));
}
for (int i = 0; i < l2.size(); i++) {
queue.add(l2.get(i));
}
ArrayList<Integer> list3 = new ArrayList<>();
while (!queue.isEmpty()) {
System.out.println(queue.peek());
list3.add(queue.poll());
}
}

有没有其他方法可以以更好的时间复杂性或空间复杂性来解决这个问题？

Answer 1

不需要使用额外的优先级队列。

This problem can be solved using 2 methods:

方法1:

首先连接两个列表，然后排序。

考虑Size of list 1 = n和Size of list 2 = m

Time complexity:O(((n+m(log(n+m((

Auxiliary Space complexity:O(n+m(

方法2:

首先对两个列表进行排序，然后合并。

Time complexity:O(nlog(n(+mlog(m(+(n+m((

Auxiliary Space complexity:O(n+m(

结论：从上述时间复杂性可以明显看出，方法2优于方法1，并且两种方法的空间复杂性保持不变。