algorithm - 如何对 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

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

这个问题可以用两种方法解决:

方法一:

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

考虑到，列表 1 的大小 = n 和 列表 2 的大小 = m

时间复杂度: O((n+m) log(n+m))

辅助空间复杂度: O(n+m)

方法二:

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

时间复杂度: O( nlog(n) + mlog(m) + (n+m))

辅助空间复杂度: O(n+m)

结论:从上述时间复杂度可以看出，方法2优于方法1，两种方法的空间复杂度保持不变。