如何以更低时间复杂度求解数组最大分组数问题

问题描述 #

给定大小为n的数组array，array[i]表示第i类物品的数量（i∈[0,n-1]），需按以下规则分组：

• 每组物品类型均不同
• 当前组大小严格大于前一组
• 物品仅可分组一次，无需全部分组

目标是找出最大可创建的分组数。

示例：n=5，array=[2,3,1,4,2]，最优分组可创建4组。

原方案的问题 #

采用最大优先队列（大顶堆）的常规思路是：每次取出数量最多的若干元素组成一组，将每个元素数量减1后放回堆，重复操作直到无法组成更大的组。但当array[i]达到1e9量级时，循环次数会直接飙升到1e9，时间复杂度为O(k log n)（k为分组总次数），完全无法处理大数据量场景。

高效解法：排序+贪心（O(n log n)时间复杂度） #

核心思路 #

通过排序+贪心策略，无需重复操作元素数量，仅需一次遍历即可计算出最大分组数：

1. 将数组按升序排序，让数量少的物品在前，数量多的在后。
2. 维护一个计数器count，表示当前能形成的最大分组数。遍历排序后的数组，若当前物品数量num > count，说明该物品可以支撑新增一组（因为当前已有count组，该物品的数量足够多，能在第count+1组中加入一个该类型物品），此时将count加1。

逻辑验证（针对示例） #

示例数组排序后为[1,2,2,3,4]：

• 初始count=0，1>0 → count=1（该物品可在第1组用1次）
• 2>1 → count=2（该物品可在第1、2组各用1次）
• 2不大于2 → 无法新增分组（该物品最多只能支撑2组）
• 3>2 → count=3（该物品可支撑前3组）
• 4>3 → count=4（该物品可支撑前4组）

最终得到最大分组数为4，与示例结果一致。

Java代码实现 #

import java.util.Arrays;

public class MaxGroupCount {
    public static int maxGroups(int[] array) {
        Arrays.sort(array);
        int count = 0;
        for (int num : array) {
            if (num > count) {
                count++;
            }
        }
        return count;
    }

    public static void main(String[] args) {
        int[] testArray = {2, 3, 1, 4, 2};
        System.out.println(maxGroups(testArray)); // 输出4
    }
}

复杂度分析 #

• 排序阶段：O(n log n)，这是算法的时间瓶颈，完全适配n≤1e5的场景。
• 遍历阶段：O(n)，与数组元素大小无关，即使array[i]达到1e9也不会影响效率。

内容的提问来源于stack exchange，提问作者CodeCrusader