Поиск максимальных групп за меньшую временную сложность ⇐ JAVA

[Anonymous]

У меня есть массив размера n, массив представляет количество элементов конкретного типа, где i находится в диапазоне от 0 до n-1 .
Я хочу упаковать элементы в группах, следующие ниже. /> [*] Текущий размер группы должен быть строго больше, чем группа, образованная в предыдущей партии. item. < /li>
< /ul>
Найдите максимальное количество групп, которые мы можем создать. От 0 до n-1 . Таким образом, количество элементов конкретного типа I (0 ≤ i ≤ n-1) определяется Array .
Пример n = 5 < /strong>

array = [2, 3, 1, 4, 2] < /strong> < /p>
Оптимальный способ создания групп:

• Первая группа содержит 1 элемент элемента Тип 4 . Остальные элементы = [2, 3, 1, 4, 1] .
• Вторая группа содержит 2 элемента типов элементов: 0 и 1 . Остальные элементы = [1, 2, 1, 4, 1] .
• Третья группа содержит 3 элемента типов элементов: 0, 1 и 3 . Остальные элементы = [0, 1, 1, 3,1] .
• Четвертая группа содержит 4 элементы типов продукта: 1, 2, 3 и 4 . Оставшиеся элементы = [0, 0, 0, 2, 0] .

Наконец, у нас есть 2 оставшиеся элементы , но наша следующая группа нуждается в 5 элементах разных типов (различные).
Поэтому может быть подготовлено только 4 группы, что максимально возможно.
< P> Я решил, используя ниже код: < /p>

Код: Выделить всё

import java.util.*;

public class Main {
public static int solve(List array) {
PriorityQueue maxHeap = new PriorityQueue(Collections.reverseOrder());
for (int e : array) {
if (e > 0)
maxHeap.offer(e);
}

int groups = 0;
int size = 1;
while (true) {
List tempList = new ArrayList();
int itemsAdded = 0;
while (!maxHeap.isEmpty() && itemsAdded < size) {
int count = maxHeap.poll();
itemsAdded++;
if (count > 1) {
tempList.add(count - 1);
}
}

if (itemsAdded < size)
break;

for (int count : tempList) {
maxHeap.offer(count);
}

groups++;
size++;
}
return groups;
}

public static void main(String[] args) {
// Test cases
List ar1 = Arrays.asList(2, 3, 1, 4, 2);
System.out.println(solve(ar1)); // Output: 4

List ar2 = Arrays.asList(1, 2, 7);
System.out.println(solve(ar2)); // Output: 3

List ar3 = Arrays.asList(1, 2, 8, 9);
System.out.println(solve(ar3)); // Output: 4

List ar4 = Arrays.asList(12, 12, 11, 11, 8, 1, 1);
System.out.println(solve(ar4)); // Output: 6
}
}
< /code>
 ограничения: < /strong>
n находится в диапазоне от 1 до 10^5
array [i] равен от 0 до 10^9 < / p>
Если размер ввода большой, вышеуказанный код не удается с ошибками тайм-аута, как решить это за меньшую временную сложность? < /p>
Также я ушел Через ответ, предоставленный моему сообщению Ravensport < /p>
size = 1
LOOP
if count of different item types in input array < size
STOP
select size items of different types from input array,
using the items that have largest same type count
add select to output groups
remove select from input array
size++
ENDLOOP

Здесь цикл заканчивается только тогда, когда типы элементов меньше, чем размер, поэтому, если размер входа большой, цикл требует больше времени для обработки элементов, которые приводит к ошибкам времени.
Какой правильный подход для решения этой проблемы в меньшей сложности времени. < /p>

Подробнее здесь: https://stackoverflow.com/questions/793 ... complexity