思维+排序，LeetCode 2860. 让所有学生保持开心的分组方法数
目录
一、题目
1、题目描述
2、接口描述
python3
cpp
C#
3、原题链接
二、解题报告
1、思路分析
2、复杂度
3、代码详解
python3
cpp
C#
一、题目
1、题目描述
给你一个下标从 0 开始、长度为
n的整数数组nums，其中n是班级中学生的总数。班主任希望能够在让所有学生保持开心的情况下选出一组学生：如果能够满足下述两个条件之一，则认为第
i位学生将会保持开心：
- 这位学生被选中，并且被选中的学生人数 严格大于
nums[i]。- 这位学生没有被选中，并且被选中的学生人数 严格小于
nums[i]。返回能够满足让所有学生保持开心的分组方法的数目。
2、接口描述
python3
class Solution:def countWays(self, nums: List[int]) -> int:cpp
class Solution {
public:int countWays(vector<int>& nums) {}
};C#
public class Solution {public int CountWays(IList<int> nums) {}
}3、原题链接
2860. 让所有学生保持开心的分组方法数
二、解题报告
1、思路分析
考虑将原数组排序
我们此时一个学生一旦选择，因为前面的都比他小所以前面的都要选
能选的前提就是后面挨着那个比他大
由于值域在n以内，可以用计数排序代替快排
2、复杂度
时间复杂度： O(N)空间复杂度：O(N)
3、代码详解
python3
class Solution:def countWays(self, nums: List[int]) -> int:n = len(nums)cnt = Counter(nums)nums = []for x in range(n + 1):while cnt[x]:cnt[x] -= 1nums.append(x)res = nums[0] > 0for i in range(1, n):if nums[i - 1] < i < nums[i]:res += 1return res + 1cpp
class Solution {
public:int countWays(vector<int>& a) {int n = a.size();std::vector<int> cnt(n + 1);for (int x : a) ++ cnt[x];a.clear();for (int i = 0; i <= n; ++ i)while (cnt[i] --)a.push_back(i);int res = a[0] > 0;for (int i = 1; i < n; ++ i)if (a[i - 1] < i && i < a[i])++ res;return res + 1;}
};
C#
public class Solution
{public int CountWays(IList<int> nums){int n = nums.Count;IList<int> a = new List<int>();int[] cnt = new int[n + 1];foreach(int x in nums) ++ cnt[x];for (int i = 0; i < n; ++ i)while (cnt[i] -- > 0)a.Add(i);int res = a[0] > 0 ? 2 : 1;for (int i = 1; i < n; ++ i){if (i > a[i - 1] && i < a[i])++ res;}return res;}
}