class Solution {
public:
int countWays(vector<int>& nums) {
}
};
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 <= nums.length <= 1050 <= nums[i] < nums.length原站题解
python3 解法, 执行用时: 120 ms, 内存消耗: 25.4 MB, 提交时间: 2023-09-17 22:35:37
class Solution:
def countWays(self, nums: List[int]) -> int:
nums.sort()
n = len(nums)
ans = nums[0] > 0
for i, (x, y) in enumerate(pairwise(nums)):
if x < i + 1 < y:
ans += 1
return ans + 1
java 解法, 执行用时: 21 ms, 内存消耗: 55 MB, 提交时间: 2023-09-17 22:35:21
class Solution {
public int countWays(List<Integer> nums) {
int[] a = nums.stream().mapToInt(i -> i).toArray();
Arrays.sort(a);
int n = a.length;
int ans = a[0] > 0 ? 1 : 0;
for (int i = 0; i < n - 1; i++) {
if (a[i] < i + 1 && i + 1 < a[i + 1]) {
ans++;
}
}
return ans + 1;
}
}
cpp 解法, 执行用时: 96 ms, 内存消耗: 70.6 MB, 提交时间: 2023-09-17 22:35:11
class Solution {
public:
int countWays(vector<int> &nums) {
sort(nums.begin(), nums.end());
int n = nums.size();
int ans = nums[0] > 0;
for (int i = 0; i < n - 1; i++) {
if (nums[i] < i + 1 && i + 1 < nums[i + 1]) {
ans++;
}
}
return ans + 1;
}
};
golang 解法, 执行用时: 100 ms, 内存消耗: 7.8 MB, 提交时间: 2023-09-17 22:34:56
func countWays(nums []int) (ans int) {
sort.Ints(nums)
if nums[0] > 0 {
ans++
}
for i, x := range nums {
if x < i+1 && (i == len(nums)-1 || i+1 < nums[i+1]) {
ans++
}
}
return
}
javascript 解法, 执行用时: 144 ms, 内存消耗: 51.7 MB, 提交时间: 2023-09-17 22:34:43
/**
* @param {number[]} nums
* @return {number}
*/
var countWays = function (nums) {
nums.sort((a, b) => a - b);
const n = nums.length;
let ans = nums[0] > 0 ? 1 : 0;
for (let i = 0; i < n - 1; i++) {
if (nums[i] < i + 1 && i + 1 < nums[i + 1]) {
ans++;
}
}
return ans + 1;
};