[M排序] lc2860. 让所有学生保持开心的分组方法数(排序+贪心+简洁代码实现+思维)

本文主要是介绍[M排序] lc2860. 让所有学生保持开心的分组方法数(排序+贪心+简洁代码实现+思维)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

文章目录

- 1. 题目来源
- 2. 题目解析

1. 题目来源

链接：2860. 让所有学生保持开心的分组方法数

题单：

思维
- 01.1、思维

2. 题目解析

有一定的思考难度，不太好归类，就放到思维里面吧。

思路：

首先分析题目中的一些关键信息，能得出来，选法是唯一的，且选的话，会把小于当前值的前面部分全部选了。
那么此时问题就转化为选0、选1、选2…选n 个的问题了。
判断条件此时也很简单。
选 k 个，那么选中的最大值需要严格小于 k，未选中的最小值需要严格大于 k 即可。

具体证明，看靠前题解即可。描述起来有点困难，不赘述。

代码实现上需要注意下，不需要将未选择、全选，当做特殊情况处理，一开始直接根据下标考虑，直接从下标 0 开始判断，且最终直接来了个 i+1 的判断逻辑，遗漏了这两种情况。

官解中根据划分长度来考虑会更加合适，即：枚举分组长度为 0、1、2、3、…n 这样子更加合适。包含了这两种特殊的情况。

学习下特判少的写法，更不易出错。

时间复杂度： $O (n)$
空间复杂度： $O (1)$

一开始的写法

class Solution {
public:int countWays(vector<int>& nums) {int n = nums.size();sort(nums.begin(), nums.end());int res = 0;for (int i = 0; i < n; i ++ ) {int cnt = i + 1;bool flag1 = false, flag2 = false;if (cnt > nums[i]) flag1 = true;if (i + 1 < n && nums[i + 1] > cnt) flag2 = true;if (flag1 && flag2) res ++ ;}// 未选中if (nums[0] > 0) res ++;// 全选中if (nums.back() < n) res ++ ;return res;}
};

简洁写法：

class Solution {
public:int countWays(vector<int>& nums) {int n = nums.size();sort(nums.begin(), nums.end());int res = 0;for (int k = 0; k <= n; k ++ ) {if (k > 0 && nums[k - 1] >= k) continue; // k=n,n个全选,判断最大值是否小于k个if (k < n && nums[k] <= k) continue; // k=0,0个全不选,判断最小值是否大于kres ++ ;}return res;}
};