2024-09-04:用 go 语言,给定一个长度为 n 的数组 happiness,表示每个孩子的幸福值,以及一个正整数 k,我们需要从这 n 个孩子中选出 k 个孩子。 在筛选过程中,每轮选择一个孩子时,所有尚未选
2024-09-04:用 go 语言,给定一个长度为 n 的数组 happiness,表示每个孩子的幸福值,以及一个正整数 k,我们需要从这 n 个孩子中选出 k 个孩子。
在筛选过程中,每轮选择一个孩子时,所有尚未选中的孩子的幸福值都会减少 1。需要注意的是,幸福值不能降低到负数,只有在其为正数时才能减少。
我们的目标是尽可能使选中的 k 个孩子的幸福值之和最大化。
输入:happiness = [1,2,3], k = 2。
输出:4。
解释:按以下方式选择 2 个孩子:
1.选择幸福值为 3 的孩子。剩余孩子的幸福值变为 [0,1] 。
2.选择幸福值为 1 的孩子。剩余孩子的幸福值变为 [0] 。注意幸福值不能小于 0 。
所选孩子的幸福值之和为 3 + 1 = 4 。
答案 2024-09-04:
题目来自 leetcode3075。
大体步骤如下:
1.对孩子的幸福值数组 happiness 进行降序排序。
2.从排序后的数组中选择前 k 个幸福值最高的孩子。这些孩子的幸福值之和即为所求。
3.在选出的 k 个孩子中,逐个孩子判断幸福值是否大于等于当前所在位置的索引值,如果是,将幸福值与当前索引值相减,并累加到最终的结果中,表示该孩子的贡献幸福值。
4.最终返回累加的结果作为最大化幸福值之和的输出。
时间复杂度分析:
排序的时间复杂度为 O(n*log(n)),n 为孩子的数量。
选 k 个孩子时,需要遍历最多 k 个元素,时间复杂度为 O(k)。
因此,总的时间复杂度为 O(n*log(n) + k)。
空间复杂度分析:
需要常量级别的额外空间来进行计算,因此总的额外空间复杂度可以看作是 O(1)。
Go 完整代码如下:
Rust 完整代码如下:
版权声明: 本文为 InfoQ 作者【福大大架构师每日一题】的原创文章。
原文链接:【http://xie.infoq.cn/article/6088a94741c236c25c2ddae6a】。
本文遵守【CC-BY 4.0】协议,转载请保留原文出处及本版权声明。
评论