目标
给你一个下标从 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^5
- 0 <= nums[i] < nums.length
思路
从数组中选择一组元素，使之满足该组元素个数严格大于组中所有元素值并且严格小于未被选择的元素值，求满足条件的所有选择数。
注意到元素值不超过数组长度，可以先统计各元素值的出现次数 cnt[i]，然后遍历 cnt。
这道题的关键是要意识到：值相同的元素要么同时被选，要么同时不被选。因为选择的元素个数 sum 应该大于所有选择的元素值，小于所有未选择的元素值，一个元素不可能既小于 sum 又大于 sum。题目的本质是将学生成两组（被选择的和未被选择的），选择的标准是根据所选人数动态变化的，水平相同的学生要么都选，要么都不选，要一碗水端平，这就是题目名想要表达的处世哲学吧。
- 当
cnt[0] == 0时，说明所有元素都大于0，因此可以一个都不选。 - 当
cnt[i] != 0时，如果我们想要选择这些元素值为i的学生，需要满足选择后的学生总数sum大于 i，并且cnt[i+1] ~ cnt[sum]应该都为0，否则就存在小于sum但是未被选的学生了。
官网题解使用的是排序，满足 sorted[i - 1] < i && i < sorted[i] 时累加计数。不过排序的复杂度是O(nlogn)，其实我们的计数数组也是有序的，算是计数排序吧，时间复杂度为O(n)。
代码
/**
* @date 2024-09-04 10:29
*/
public class CountWays2860 {
public int countWays(List<Integer> nums) {
int n = nums.size();
int[] cnt = new int[n];
for (Integer num : nums) {
cnt[num]++;
}
int[] prefix = new int[n];
for (int i = 1; i < n; i++) {
prefix[i] = prefix[i - 1] + cnt[i];
}
int res = cnt[0] > 0 ? 0 : 1;
int sum = 0;
for (int i = 0; i < n; i++) {
sum += cnt[i];
if (sum > i && cnt[i] != 0 && prefix[Math.min(n - 1, sum)] == prefix[i]) {
res++;
}
}
return res;
}
}
性能
