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

2024-09-04

题目:

给你一个下标从 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

思路:

在选择学生人数固定的时候,选择方案是否唯一呢?
假设恰好选 k 个学生,那么:
	所有 nums[i] < k 的学生都要选;
	所有 nums[i] > k 的都不能选;
	不能出现 nums[i] = k 的情况,因为每个学生只有选或不选两种可能。
这意味着在选择学生人数固定的时候,选择方案是唯一的。把 nums 从小到大排序后,唯一性可以更明显地看出来:
	以 k 为分界线,左边的都要选,右边的都不能选。
具体地,如果选 nums[i − 1] 而不选 nums[i],由于数组已排序,我们必须要选下标为 0, 1, 2, ⋯, i − 1 的学生,一共 i 个,而下标 ≥ i 的学生都不能选,所以需要满足 nums[i−1] < i < nums[i]
枚举 i = 1, 2, ⋯, n − 1,如果上式成立,就意味着我们可以选 i 个学生,算作一种方案。
特殊情况:
	如果 nums[0] > 0,那么可以一个学生都不选。
	如果 nums[n − 1] < n,那么可以所有学生都选。由于数据范围保证 nums[i] < n,所以这种方案一定存在。

代码:

class Solution {
public:
    int countWays(vector<int>& nums) {
        ranges::sort(nums);
        int ans = nums[0] > 0; // 一个学生都不选
        for (int i = 1; i < nums.size(); i++) {
            ans += nums[i - 1] < i && i < nums[i];
        }
        return ans + 1; // 一定可以都选
    }
};