Medium

题目描述

给你一个下标从 0 开始、长度为 n 的整数数组 nums，其中 n 是班级中学生的总数。班主任希望选择一组学生，使得所有学生都保持快乐。

如果满足下述两个条件之一，第 i 个学生将会保持快乐：

  • 这名学生被选中，且被选中的学生人数 严格大于 nums[i] 。
  • 这名学生没有被选中，且被选中的学生人数 严格小于 nums[i] 。

返回能够满足让所有学生都快乐的方案数。

示例 1：

输入：nums = [1,1]
输出：2
解释：
有 2 种可能的方法：
- 班主任没有选择任何学生。
- 班主任选择所有学生形成一组。
如果班主任仅选择一个学生来组成小组，那么两个学生都无法保持快乐。因此，仅有 2 种可能的方法。

示例 2：

输入：nums = [6,0,3,3,6,7,2,7]
输出：3
解释：
有 3 种可能的方法：
- 班主任选择下标为 1 的学生形成一组。
- 班主任选择下标为 1、2、3、6 的学生形成一组。
- 班主任选择所有学生形成一组。

提示：

  • 1 <= nums.length <= 10^5
  • 0 <= nums[i] < nums.length

解题思路

这道题的核心思想是理解学生快乐的条件，并找出所有可能的选择方案数。

首先分析题意：

  • 如果学生被选中，那么选中的总人数必须严格大于该学生的期望值
  • 如果学生没被选中，那么选中的总人数必须严格小于该学生的期望值

关键观察：对于任何有效的选择方案，如果我们按照 nums 值排序，那么必然存在一个分界点，使得分界点左侧的学生都被选中，右侧的学生都不被选中。这是因为如果一个期望值较小的学生不被选中，那么期望值更大的学生也不应该被选中。

解题步骤：

  1. 对数组进行排序
  2. 枚举所有可能的选择人数 k（从 0 到 n）
  3. 对于每个 k，检查是否满足所有学生的快乐条件：
    • 前 k 个学生（被选中）：选择人数 k 必须严格大于他们的期望值
    • 后 n-k 个学生（未被选中）：选择人数 k 必须严格小于他们的期望值

这样我们就能统计出所有有效的方案数。

代码实现

class Solution {
public:
    int countWays(vector<int>& nums) {
        sort(nums.begin(), nums.end());
        int n = nums.size();
        int ways = 0;
        
        for (int k = 0; k <= n; k++) {
            bool valid = true;
            
            // 检查被选中的学生是否快乐
            for (int i = 0; i < k; i++) {
                if (k <= nums[i]) {
                    valid = false;
                    break;
                }
            }
            
            // 检查未被选中的学生是否快乐
            if (valid) {
                for (int i = k; i < n; i++) {
                    if (k >= nums[i]) {
                        valid = false;
                        break;
                    }
                }
            }
            
            if (valid) {
                ways++;
            }
        }
        
        return ways;
    }
};

class Solution:
    def countWays(self, nums: List[int]) -> int:
        nums.sort()
        n = len(nums)
        ways = 0
        
        for k in range(n + 1):
            valid = True
            
            # 检查被选中的学生是否快乐
            for i in range(k):
                if k <= nums[i]:
                    valid = False
                    break
            
            # 检查未被选中的学生是否快乐
            if valid:
                for i in range(k, n):
                    if k >= nums[i]:
                        valid = False
                        break
            
            if valid:
                ways += 1
        
        return ways

public class Solution {
    public int CountWays(IList<int> nums) {
        var sortedNums = nums.OrderBy(x => x).ToArray();
        int n = sortedNums.Length;
        int ways = 0;
        
        for (int k = 0; k <= n; k++) {
            bool valid = true;
            
            // 检查被选中的学生是否快乐
            for (int i = 0; i < k; i++) {
                if (k <= sortedNums[i]) {
                    valid = false;
                    break;
                }
            }
            
            // 检查未被选中的学生是否快乐
            if (valid) {
                for (int i = k; i < n; i++) {
                    if (k >= sortedNums[i]) {
                        valid = false;
                        break;
                    }
                }
            }
            
            if (valid) {
                ways++;
            }
        }
        
        return ways;
    }
}

var countWays = function(nums) {
    nums.sort((a, b) => a - b);
    const n = nums.length;
    let ways = 0;
    
    for (let k = 0; k <= n; k++) {
        let valid = true;
        
        // 检查被选中的学生是否快乐
        for (let i = 0; i < k; i++) {
            if (k <= nums[i]) {
                valid = false;
                break;
            }
        }
        
        // 检查未被选中的学生是否快乐
        if (valid) {
            for (let i = k; i < n; i++) {
                if (k >= nums[i]) {
                    valid = false;
                    break;
                }
            }
        }
        
        if (valid) {
            ways++;
        }
    }
    
    return ways;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度说明
时间复杂度O(n²)外层循环 O(n)，内层最坏情况遍历 O(n)，排序 O(n log n)
空间复杂度O(1)除了排序可能需要的额外空间外，只使用常量额外空间