题目描述
给你一个下标从 0 开始、长度为 n
的整数数组 nums
,其中 n
是班级中学生的总数。班主任希望能够在让所有学生保持开心的情况下选出一组学生:
如果能够满足下述两个条件之一,则认为第 i
位学生将会保持开心:
- 这位学生被选中,并且被选中的学生人数 严格大于
nums[i]
。 - 这位学生没有被选中,并且被选中的学生人数 严格小于
nums[i]
。
返回能够满足让所有学生保持开心的分组方法的数目。
样例
输入:nums = [1,1]
输出: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
算法
(贪心) $O(n \log n)$
- 注意到,在选择学生人数固定的时候,选择方案是唯一的。这是因为,在选择了 $k$ 个学生时,所有 $nums(i) < k$ 的学生都要选,所有 $nums(i) > k$ 的都不能选,并且不能出现 $nums(i) = k$ 的情况,这意味着选择方案是唯一的,即选择 $nums(i)$ 最小的 $k$ 个学生。
- 将 $nums$ 从小到大排序。
- 从 $0$ 开始枚举选择的人数,同时按顺序从小到大遍历数组,如果能满足以上的条件,则累加答案。
时间复杂度
- 排序的时间复杂度为 $O(n \log n)$。
- 排序后,遍历数组一次。
- 故时间复杂度为 $O(n \log n)$。
空间复杂度
- 需要 $O(\log n)$ 的额外空间存储排序的系统栈。
C++ 代码
class Solution {
public:
int countWays(vector<int>& nums) {
sort(nums.begin(), nums.end());
const int n = nums.size();
int ans = 0;
for (int i = 0; i <= n; i++) {
if (i > 0 && i <= nums[i - 1])
continue;
if (i < n && i >= nums[i])
continue;
++ans;
}
return ans;
}
};