1103.分糖果

解题思路

解法一：暴力法

对小朋友们进行遍历，每次都发小朋友们应得数量的糖，直到剩下的糖不足以分发应得数量，就直接给最后那位倒霉孩子。

复杂度分析
时间复杂度：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