寻求O(n)时间复杂度解法：最小化技能分组数（组内技能差≤k）

问题回顾 #

给定技能数组skills，每个元素代表学生的技能水平，需将学生分组，要求同一组内任意两人的技能最大差值不超过k，求最少分组数。已知先排序再遍历的O(n logn)解法，现寻求O(n)复杂度的实现方案。

示例：

skills = [7,2,9,1,13,4]
k = 3
# 最少分组数 = 3
分组结果：([1,2,4], [7,9], [13])

O(n)解法思路 #

要实现O(n)复杂度，核心是利用计数排序/桶排序的思想，但该方案仅适用于技能值的取值范围有限且可接受的场景（比如技能值在0~1e5这类量级）。具体逻辑如下：

• 先遍历数组统计每个技能值的出现次数，避免排序操作；
• 从最小技能值到最大技能值依次处理，维护当前组的起始技能值，只要后续技能值不超过当前起始值 +k，就可以归入当前组；一旦超出则新建分组，更新起始值。

具体实现步骤 #

1. 找出数组中的最小/最大技能值，确定遍历范围；
2. 创建计数数组，记录每个技能值对应的学生数量；
3. 初始化分组数和当前组起始值，遍历所有可能的技能值：
   • 若当前技能值无学生，直接跳过；
   • 若当前无分组，或当前技能值超出当前组的差值限制，则新建分组并更新起始值；
4. 最终分组数即为答案。

代码实现（Python） #

def min_groups(skills, k):
    if not skills:
        return 0
    min_skill = min(skills)
    max_skill = max(skills)
    # 构建计数数组，统计每个技能的学生数量
    count = [0] * (max_skill - min_skill + 1)
    for skill in skills:
        count[skill - min_skill] += 1
    
    group_count = 0
    current_group_start = -1
    # 按技能值从小到大遍历
    for skill_val in range(min_skill, max_skill + 1):
        idx = skill_val - min_skill
        if count[idx] == 0:
            continue
        # 需要新建分组的情况
        if current_group_start == -1 or skill_val > current_group_start + k:
            group_count += 1
            current_group_start = skill_val
    return group_count

# 测试示例
skills = [7,2,9,1,13,4]
k = 3
print(min_groups(skills, k))  # 输出：3

适用场景与局限性 #

• 适用场景：当技能值的取值范围不大（比如最大值与最小值的差远小于数组长度n），此时计数数组的空间开销可接受，整体时间复杂度为O(n + M)（M为技能值范围），等价于O(n)；
• 局限性：如果技能值范围极大（比如1到1e9），计数数组的空间会爆炸，此时O(n logn)的排序遍历解法反而更实用，因为排序的空间开销远低于计数排序。

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