100040. 讓所有學生保持開心的分組方法數

給你一個下標從 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. 排序
2. 遍歷選擇0,1,2,....n是否可行
3. 盡可能選擇小的

為什么能夠想到呢？一個是看數據范圍：O(n)或者O(nlogn),另外一個就是在想怎么選擇的時候：

1. 沒有選中，那么選中的數目要嚴格小于nums[i] -> 沒選中的nums[i]要盡可能大
2. 選中，那么選中的數目要嚴格大于nums[i] -> 選中的nums[i]要盡可能小

code

class Solution {
public:
    
    //沒有被選中，選中人數嚴格小于nums[i]
    //被選中，選中人數嚴格大于nums[i]
    //讓所有學生都開心的分組數目
    //10 ^ 5
    //O(n) or O(nlogn)
    //排序
    
    //遍歷
    //選中人數k
    //
    int countWays(vector<int>& nums) {
        
        sort(nums.begin(),nums.end());
        int ans = 0,k = 0;
        
        if(k < nums[0]) ans ++;
        
        int i;
        for(i = 0;i < nums.size() - 1;i ++)
        {
            k ++ ;
            if(k < nums[i + 1] && k > nums[i]) ans ++;
        }
        
        k ++;
        if(k > nums[i]) ans ++;
        
        return ans;
        
        
    }
};