题目:
给你一个下标从 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; // 一定可以都选
}
};