Tuesday, February 13, 2018

[LeetCode]Rabbits in Forest



题目的描述可以观察出来,如果两个兔子的颜色一样,那么他们报的数字一定一样。但是反过来不一定。那么我们如何确定报相同数字的兔子他们是否拥有相同的颜色呢?根据题目的要求,我们要让兔子的总数越小越好,假设有n个兔子报的数字为m,有以下几种情况:

  • n < m + 1, 为了让兔子总数最小,我们可以让这n个兔子都有相同的颜色c,颜色为c的兔子总数根据报数有m + 1个(包括报数者自己)
  • n == m + 1同理,n个兔子可以有相同的颜色c,颜色为c的兔子总共有m + 1个
  • n > m + 1, 我们可以先让m + 1个兔子有相同的颜色,更新n = n - (m + 1),继续算,直到n小于等于0
常数空间,假设总共有n个兔子,时间复杂度O(n),代码如下:


No comments:

Post a Comment