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

[Anonymous]

У меня есть массив размера n, массив представляет количество элементов конкретного типа, где i находится в диапазоне от 0 до n-1 .
Я хочу упаковать элементы в группах, следующие ниже. /> [*] Текущий размер группы должен быть строго выше, чем группа, образованная в предыдущей партии. . < /li>
< /ul>
Найдите максимальное количество групп, которые мы можем создать. к 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
}
}

Если размер ввода большой выше, код не удастся с ошибками времени, как решить это за меньшей сложности времени.

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