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

题目描述：

给你一个下标从 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 <= 105
• 0 <= nums[i] < nums.length

---

解题分析及思路：

方法：排序 + 枚举

对于每一个学生 i ，当其被选中时，需要严格满足：

• 选中学生数量 count 严格大于 nums[i]
• 选中学生数量 count 严格小于 nums[i + 1]

因为要选中学生i，那么所有小于 nums[i] 的学生都应该被选中，所以为了更好的判断，我们需要将数组 nums 排序。

那么，如果选中学生 i （也就是不选中 i+1）的情况，必须满足：i + 1 > nums[i] 并且 i + 1 < nums[i + 1]

为了更好的处理所有情况，需要单独处理边界情况。

也就是未选中下标为 0 和 选中下标len(nums) - 1 的情况。

• 未选中下标为 0 的情况：如果 nums[0] != 0 ，则 res++
• 选中下标为 len(nums) - 1 的情况：因为 范围满足nums[i] < nums.length，所以选中下标为 len(nums) - 1 的情况必然满足，所以 res++

思路：

func countWays(nums []int) int {
	sort.Ints(nums)
	// 边界 下标：len(nums) - 1
	var res int = 1
	// 边界 下标：0
	if nums[0] != 0 {
		res++
	}
	for index := 0; index < len(nums)-1; index++ {
		if index+1 > nums[index] && index+1 < nums[index+1] {
			res++
		}
	}
	return res
}

复杂度：

• 时间复杂度：O(N * log N)
• 空间复杂度：O(logN)

执行结果：

• 执行耗时:76 ms,击败了53.33% 的Go用户
• 内存消耗:8.3 MB,击败了13.33% 的Go用户