Получение N отсортированных элементов из массива отсортированных массивов

Question

У меня есть многомерный массив дат, строго ArrayList<ArrayList<Date>>. Мне нужно создать новый одномерный ArrayList<Date>, состоящий из элементов во всех массивах вышеупомянутого многомерного.

Моя первая мысль состояла в том, чтобы объединить всех арраистов и отсортировать их, но так как я не знаю количества элементов на каждом уровне и нуждаюсь только в определенном количестве элементов в сгенерированном массиве, это было бы бит слишком большой объем памяти и процессора. Я имею в виду, если я присоединяюсь ко всем Date элементам в одном ArrayList<Date>, я мог бы закончить работу с тысячами дат в аранжировщике ... чтобы в конце концов подрезать его до первого 20. Вот почему я отказался от этого решения.

Итак, какой алгоритм я мог использовать для сортировки элементов из N (или 2) уровней в 1?

Редактировать

ArrayList<Date> a1 = new ArrayList<Date>(); 
a1.add(new Date(15)); 
a1.add(new Date(16)); 
a1.add(new Date(23)); 

ArrayList<Date> a2 = new ArrayList<Date>(); 
a2.add(new Date(1)); 
a2.add(new Date(25)); 
a2.add(new Date(89)); 

ArrayList<Date> a3 = new ArrayList<Date>(); 
a3.add(new Date(64)); 
a3.add(new Date(72)); 
a3.add(new Date(73)); 

ArrayList<ArrayList<Date>> b = new ArrayList<ArrayList<Date>>(); 
b.add(a1); 
b.add(a2); 
b.add(a3); 

Мне нужно реализовать getLatestDates(ArryList<ArrayList<Date>>, Integer) таким образом, что бы вернуть это:

getLatestDates(b, 5) = {Date (89), Date(73), Date(72), Date(64), Date(25)}; 

В этом примере есть только 3 ArrayList, но на практике я не буду знайте номер, поэтому я не думаю, что лучшим решением для мобильного устройства является объединение всех арраистов второго уровня и сортировка нового большого, если будет использоваться только несколько элементов.

Answer 1

В соответствии с вашим описанием проблемы, некоторые решения я могу думать о том, являются:

1. Ofcourse одного вы предложили, т.е. добавление всех массивов, а затем сортировать их и принимать первые 20 из них.
2. Отсортируйте каждый из этих внутренних массивов индивидуально, а затем выполните процедуру слияния, как процедура, из алгоритма сортировки слияния, чтобы объединить первые 20 элементов из всех этих внутренних массивов и вырваться из цикла слияния при каждом желаемом количестве элементов (например, 20 элементов).
3. Сортировка каждой из этих внутренних массивов при помещении в них дат. Чтобы вам не пришлось перебирать все последующие слова. Затем выполните процедуру слияния, как указано выше.

Если у вас есть несколько элементов в нескольких внутренних массивах, и вы хотите, чтобы у них было 20 первых, вам придется проходить через внутренние массивы так или иначе. Это три решения, которые я могу придумать, кто-то еще может добавить мой пост.

Edit:

4. Еще один подход, который я могу думать: строить очереди приоритета (мин кучи) путем сканирования всего массива внутренних массивов. Это будет дерево с ограничением глубины, т. Е. Поскольку вам нужно 20 элементов, максимальная глубина дерева может быть 4 (при условии, что корень равен 0). и максимальное количество разрешенных элементов в вашей куче будет 20. Этот подход даст вам решение в O (log N) времени. Конечно, вы потратите время O (N) на сканирование каждого предмета из всего списка и построение этой кучи может занимать дополнительное пространство.

Answer 2

Я бы предложил tournament algorithm. Это может быть довольно сложно, но даст вам время работы, линейное в всего количество элементов.

Я бы действовать следующим образом:

1. Есть турнир для каждого списка и сохранить дерево турнира (это дерево может быть довольно тривиально: для каждого элемента, сохранить список противников и результат)
2. Have турнир между победителями и хранить турнира дерева
3. Первым элементом является победителем турнира 2
4. Второй элемент находится среди проигравших победителя в любом турнире 1 или 2 турнира
5. Третий элемент среди проигравших NR2 в любом турнире 1 или 2 турнира
6. И так далее ...