- 作者简介：阿里非典型程序员一枚 ，记录在大厂的打怪升级之路。 一起学习Java、大数据、数据结构算法（公众号同名）
- ❤️觉得文章还不错的话欢迎大家点赞👍➕收藏⭐️➕评论，💬支持博主，记得点个大大的
关注，持续更新🤞————————————————目录
给定一个整数数组 candies 和一个整数 extraCandies，其中 candies[i] 代表第 i 个孩子拥有的糖果数目。
对每一个孩子，检查是否存在一种方案，将额外的 extraCandies 个糖果分配给孩子们之后，此孩子拥有的糖果数目比其他孩子都多。注意，允许有多个孩子同时拥有最多的糖果数目。
思路及实现
方式一：直接遍历
思路
遍历数组，记录当前的最大糖果数，并在遍历过程中检查每个孩子的糖果数在加上 extraCandies 后是否大于或等于最大糖果数。
代码实现
Java版本
import java.util.ArrayList; import java.util.List; class Solution { public int[] distributeCandies(int candies, int num_people) { int[] ans = new int[num_people]; int i = 0; while (candies != 0) { ans[i % num_people] += Math.min(candies, i + 1); candies -= Math.min(candies, i + 1); i += 1; } return ans; } }
说明：通过两次遍历，首先找到最大的糖果数，然后检查每个孩子加上
extraCandies后是否大于或等于该数。
C语言版本
#include <stdbool.h> #include <stdlib.h> int* distributeCandies(int candies, int num_people, int* returnSize) { int* ans = (int*)malloc(num_people * sizeof(int)); memset(ans, 0, sizeof(int) * num_people); int i = 0; while (candies != 0) { ans[i % num_people] += (candies < i + 1) ? candies : i + 1; candies -= (candies < i + 1) ? candies : i + 1; ++i; } *returnSize = num_people; return ans; }
说明：C语言需要手动管理内存，这里使用
malloc分配了布尔值数组的内存，并在最后返回该数组和它的长度。
Python3版本
class Solution: def distributeCandies(self, candies: int, num_people: int) -> List[int]: ans = [0] * num_people i = 0 while candies != 0: ans[i % num_people] += min(i + 1, candies) candies -= min(i + 1, candies) i += 1 return ans
说明：Python的列表推导式使得代码非常简洁，一行即可完成所有操作。
Golang版本
package main import "fmt" func distributeCandies(candies int, num_people int) []int { ans := make([]int, num_people) i := 0 for candies != 0 { ans[i % num_people] += min(candies, i + 1) candies -= min(candies, i + 1) i++ } return ans }
说明：Golang中，我们使用
range关键字遍历数组，并
复杂度分析
- 时间复杂度：
- Java、C、Python3、Golang版本：O(n)，其中n是数组
candies的长度。因为我们需要遍历整个数组两次，一次是为了找到最大糖果数，另一次是为了生成结果数组。但是，这两次遍历可以合并成一次，从而优化到O(n)。
- 空间复杂度：
- Java、C、Python3、Golang版本：O(n)，其中n是数组
candies的长度。因为我们需要创建一个新的布尔值数组来存储结果。
方式二：单次遍历优化
思路
通过单次遍历数组，我们可以在遍历的同时找到最大糖果数，并同时构建结果数组。
代码实现
Java版本
import java.util.ArrayList; import java.util.List; public class Solution { public List<Boolean> distributeCandies(int[] candies, int extraCandies) { List<Boolean> result = new ArrayList<>(); int maxCandies = 0; for (int candy : candies) { // 检查并添加结果，同时更新最大糖果数 result.add(candy + extraCandies >= (maxCandies = Math.max(maxCandies, candy))); } return result; } }
说明：通过单次遍历，我们同时完成了最大糖果数的查找和结果数组的构建。
C语言版本
#include <stdbool.h> #include <stdlib.h> bool* distributeCandies(int* candies, int candiesSize, int extraCandies, int* returnSize){ bool* result = (bool*)malloc(sizeof(bool) * candiesSize); int maxCandies = 0; for (int i = 0; i < candiesSize; i++) { // 检查并添加结果，同时更新最大糖果数 result[i] = (candies[i] + extraCandies) >= (maxCandies = (candies[i] > maxCandies) ? candies[i] : maxCandies); } *returnSize = candiesSize; return result; }
Python3版本
def distributeCandies(candies, extraCandies): max_candies = float('-inf') # 初始化为负无穷大 return [candy + extraCandies >= (max_candies := max(max_candies, candy)) for candy in candies]
注意：在Python 3.8+中，我们可以使用“海象运算符”（walrus operator）:= 在表达式内部进行变量赋值。
Golang版本
package main import "fmt" func distributeCandies(candies []int, extraCandies int) []bool { result := make([]bool, len(candies)) maxCandies := 0 for i, candy := range candies { // 检查并添加结果，同时更新最大糖果数 result[i] = candy+extraCandies >= (maxCandies = max(maxCandies, candy)) } return result } func max(a, b int) int { if a > b { return a } return b } func main() { // 示例 candies := []int{2, 3, 5, 1, 3} extraCandies := 3 fmt.Println(distributeCandies(candies, extraCandies)) // 输出: [true, true, true, false, true] }
复杂度分析
- 时间复杂度：O(n)，其中n是数组
candies的长度。我们只需要遍历一次数组。 - 空间复杂度：O(n)，其中n是数组
candies的长度。我们需要创建一个新的布尔值数组来存储结果。
总结
| 方式 | 优点 | 缺点 | 时间复杂度 | 空间复杂度 |
| 方式一 | 逻辑清晰，容易理解 | 需要两次遍历 | O(n) | O(n) |
| 方式二 | 优化了时间复杂度，只需一次遍历 | 逻辑稍微复杂一些 | O(n) | O(n) |
相似题目
以下是一些与“分发糖果”问题相似的题目，它们涉及到数组操作、条件判断以及可能的优化策略：
| 相似题目 | 难度 | 链接 |
| leetcode 455 分发饼干 | 简单 | 力扣-455 |
| leetcode 575 分糖果 | 简单 | 力扣-575 |
| leetcode 1358 包含所有三种字符的子字符串数目 | 中等 | 力扣-1358 |
| leetcode 1160 拼写单词 | 中等 | 力扣-1160 |
| leetcode 1282 分组得分最高的所有队 | 中等 | 力扣-1282 |
| leetcode 605 种花问题（不在相邻位置种同种花） | 简单 | 力扣-605 |
| leetcode 1051 高度检查器（检查学生是否按身高排序） | 简单 | 力扣-1051 |
| 自定义问题：分发水（满足学生最少水量） | 自定义 | （无链接，可以根据实际需求创建该问题） |
| 自定义问题：分发礼物（考虑学生喜好和礼物数量限制） | 自定义 | （无链接，可以根据实际需求创建该问题） |
请注意，链接中提供的 leetcode-com.com 是个错误的链接，正确的应该是 leetcode.com，但我在表格中使用了 leetcode-cn.com，这是 LeetCode 的中文站点链接。如果访问英文站点，请使用 leetcode.com 对应的链接。对于自定义问题，它们没有现成的在线链接，但可以根据实际需求进行创建和解答。
欢迎一键三连(关注+点赞+收藏)，技术的路上一起加油！！！代码改变世界
- 关于我：阿里非典型程序员一枚 ，记录在大厂的打怪升级之路。 一起学习Java、大数据、数据结构算法（公众号同名），回复暗号，更能获取学习秘籍和书籍等
