Как отсортировать 2 несортированных списка и создать отсортированный список? - PullRequest
Новая
       22

Как отсортировать 2 несортированных списка и создать отсортированный список?

0 голосов
/ 26 октября 2019

Мне дали двух массивов, которые не были отсортированы и имеют один отсортированный список. Мне не разрешили отсортировать первые два списка.

Я просто выбросил оба списка в очередь с приоритетами, вытащил значения и поместил их в третий список. Как .. 

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());
        }

    }

Есть ли другой способ решить эту проблему с большей временной или пространственной сложностью?

1 Ответ

0 голосов
/ 26 октября 2019

Нет необходимости использовать очередь с дополнительным приоритетом.

This problem can be solved using 2 methods:

Метод 1:

Сначала объедините 2 списка изатем сортировать.

Учитывая, 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, и сложность пространства для обоих методов остается одинаковой.

...