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

[Anonymous]

У меня есть массив размером n, array представляет количество элементов определенного типа, где i находится в диапазоне от 0 до n-1.
Я хочу упаковать элементы в группы, следуя следующим правилам:

• Все элементы в группе должны быть разными.
• Текущий размер группы должен быть строго больше, чем группа, сформированная в предыдущей группе.
• Кроме того, каждый элемент можно сгруппировать только один раз, и не обязательно группировать каждый элемент.

Найдите максимальное количество групп, которые мы можем можно создавать.
Примечание. Типы элементов пронумерованы от 0 до n-1. Таким образом, количество элементов определенного типа i (0 ≤ i ≤ n-1) задается массивом.
Пример n=5

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

• Первый группа содержит 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 группы, что является максимально возможным.
Я решил, используя приведенный ниже код:

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

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

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

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