让所有学生保持开心的分组方法数

难度: Medium

给你一个下标从 0 开始、长度为 n 的整数数组 nums ，其中 n 是班级中学生的总数。班主任希望能够在让所有学生保持开心的情况下选出一组学生：

如果能够满足下述两个条件之一，则认为第 i 位学生将会保持开心：

这位学生被选中，并且被选中的学生人数 严格大于 nums[i] 。
这位学生没有被选中，并且被选中的学生人数 严格小于 nums[i] 。

返回能够满足让所有学生保持开心的分组方法的数目。

示例 1：

输入：nums = [1,1]
输出：2
解释：
有两种可行的方法：
班主任没有选中学生。
班主任选中所有学生形成一组。 
如果班主任仅选中一个学生来完成分组，那么两个学生都无法保持开心。因此，仅存在两种可行的方法。

示例 2：

输入：nums = [6,0,3,3,6,7,2,7]
输出：3
解释：
存在三种可行的方法：
班主任选中下标为 1 的学生形成一组。
班主任选中下标为 1、2、3、6 的学生形成一组。
班主任选中所有学生形成一组。

提示：

1 <= nums.length <= 10⁵
0 <= nums[i] < nums.length

Submission

运行时间: 77 ms

内存: 25.6 MB

class Solution:
    def countWays(self, nums: List[int]) -> int:
        nums.sort()
        n = len(nums)
        ans = 1
        if nums[0]:
            ans += 1
        for i in range(1, n):
            if nums[i - 1] < i < nums[i]:
                ans += 1
        return ans

Explain

题解首先对数组 nums 进行排序。排序后，可以利用数组的顺序属性来判断哪些选中的学生人数可以使全部学生保持开心。\n\n对于每个学生 i ，要满足的条件是：\n1. 如果这位学生被选中，那么至少要有 nums[i] + 1 个学生被选中（因为要严格大于 nums[i]）。\n2. 如果这位学生没有被选中，被选中的学生数必须严格小于 nums[i]。\n\n由于数组已经排序，nums[i] 是递增的，因此可以通过遍历排序后的数组，检查每个可能的学生人数 k 是否满足所有学生的开心条件：\n- nums[0] > 0 意味着没有学生被选中时，所有学生都会开心。\n- 对于 k = i (从 1 开始)，如果 nums[i-1] < i < nums[i]，则选择 i 个学生会使得所有学生保持开心。\n\n最终，算法统计并返回所有可能让学生开心的组合数量。

时间复杂度: O(n log n)

空间复杂度: O(1)

class Solution:
    def countWays(self, nums: List[int]) -> int:
        nums.sort()  # 对 nums 进行排序
        n = len(nums)  # n 是数组的长度
        ans = 1  # 初始化可行方法数至少为 1（全不选）
        if nums[0]:
            ans += 1  # 如果 nums[0] > 0，增加一种全选的方法
        for i in range(1, n):
            # 遍历每个可能的学生数 i，检查是否存在一种方式使得所有学生开心
            if nums[i - 1] < i < nums[i]:
                ans += 1  # 如果存在，增加一种方法
        return ans  # 返回总的方法数

Explore

排序数组后将学生的要求以非减序列方式组织起来，这样可以更方便地检查每个可能的学生人数k。由于数组是非减的，如果一个数k满足某个位置i的要求，那么它一定满足所有位置小于i的要求。同理，如果k不满足位置i的要求，那么它也不会满足所有位置大于i的要求。这种属性允许我们只需线性扫描一次排序后的数组，就能确定哪些学生人数k能使所有学生满意，大大提高了效率。

题解中的表述存在误导。实际上，如果`nums[0] == 0`，表示至少需要1个学生被选中以满足第一个学生的开心条件。因此，在`nums[0] == 0`的情况下我们应该增加全选的方法。如果`nums[0] > 0`，意味着即使没有学生被选中，第一个学生的要求也已经被满足，因此只需考虑全不选的方法。

条件`nums[i - 1] < i < nums[i]`意味着选中的学生数量i正好位于nums[i-1]（前一个学生需要的最少数量）和nums[i]（当前学生需要的最少数量）之间。这保证了前i个学生的需求都被满足（因为i大于他们的需求），同时不会超过第i+1个学生的需求（因为i小于该学生的需求）。这种精确匹配使所有学生都保持开心。

即使数组中有重复元素，这种方法仍然有效。重复元素意味着有多个学生具有相同的开心条件。在这种情况下，只要选择的学生数满足这些重复条件中的任何一个，就自然也满足了其他所有相同的条件。因此，重复元素不会影响这种基于排序和条件检查的方法来确定所有可能使学生开心的分组数。