解题思路
解法一:暴力法
对小朋友们进行遍历,每次都发小朋友们应得数量的糖,直到剩下的糖不足以分发应得数量,就直接给最后那位倒霉孩子。
复杂度分析
时间复杂度:O(max(sqrt{G}, N)),G 为糖果数量,N 为人数。
本方法的时间复杂度取决于循环到底走多少步。设总的步数为 s,用等差数列求和公式可以求得 s 步时发放的糖果数量为 s(s+1)/2。那么只要 s^2+s≥2G 糖果就可以保证被发完。而只要当 s≥sqrt{2G}时,就有 s^2≥2G,显然也有 s^2+s≥2G。因此可知总的步数 s≤⌈sqr{2G}⌉,时间复杂度为 O(sqrt{G})。
另外建立糖果分配数组并初值赋值需要 O(N) 的时间,因此总的时间复杂度为O(max(sqrt{G},N))。
空间复杂度:O(1),除了答案数组只需要常数空间来存储若干变量。
解法二:数学法
略
代码
class Solution:
def distributeCandies(self, candies: int, num_people: int) -> List[int]:
# 解法一:暴力法
kids = [0]*num_people
# 初始化分配轮数
i = 0
while candies>0:
# 分配糖果,并时不时的判断当前剩余糖果数够这轮分配
# 注意 i%num_people ,随着i的增长,i对num_people进行取余数就是相应小朋友的数组下标
# min的作用是,如果有一天糖不够了,就把那些最后剩余的糖给最后那个孩子
kids[i%num_people] += min(i+1, candies)
# 总糖果数减去分出的
candies -= min(i+1, candies)
# 轮数加1
i += 1
return kids
网友评论