题目

每年六一儿童节,牛客都会准备一些小礼物去看望孤儿院的小朋友,今年亦是如此。HF作为牛客的资深元老,自然也准备了一些小游戏。其中,有个游戏是这样的:首先,让小朋友们围成一个大圈。然后,他随机指定一个数m,让编号为0的小朋友开始报数。每次喊到m-1的那个小朋友要出列唱首歌,然后可以在礼品箱中任意的挑选礼物,并且不再回到圈中,从他的下一个小朋友开始,继续0…m-1报数….这样下去….直到剩下最后一个小朋友,可以不用表演,并且拿到牛客名贵的“名侦探柯南”典藏版(名额有限哦!!^_^)。请你试着想下,哪个小朋友会得到这份礼品呢？(注：小朋友的编号是从0到n-1)

如果没有小朋友，请返回-1

方法

方法：数学归纳法
参考：https://www.bbsmax.com/A/o75NvvOK5W/
时间复杂度：n

思路

通过归纳法，分析某次报数前后的情况，假设我们分析第一次报数前后情况

n个小朋友，
编号为：0，1，2，…，n-1。报数0~m-1，m-1淘汰，那么淘汰的编号是(m-1)%n = k

那么，现在场上的n-1个小朋友，
编号为：0，…，k-2，k-1，k+1，k+2，…，n-2，n-1 —— （1）
下一轮报数，对应为：n-k-1，…，n-3，n-2，0，1，…，n-k-3，n-k-2 —— （2）
上面的报数自行归纳
那么归纳一下一轮报数的结果，可以发现，经过一轮报数后，下一轮报数的编号p(x) = (x + n - k - 1) % n

这个归纳的公式有什么用？第一轮报数是n个小朋友，第二轮报数是n-1个小朋友，而上述的“下一轮报数”的编号，就是重置第二轮的n-1个小朋友的编号的结果。在此假设，我们知道n-1个小朋友，经过n-2报数后的最后小朋友的编号F(n-1, m)，那么相当于知道了“下一轮报数”编号中，哪个小朋友会胜利。那么，通过上述归纳的公式，是不是就可以知道这个编号，在n个小朋友编号中的原先位置F(n, m)，进而知道n个小朋友报数的最终胜利者

但是，上面归纳的是，（1）到（2）的关系，我们需要（2）到（1）的关系，所以我们需要求p(x)的反函数
反函数求解过程参考https://www.bbsmax.com/A/o75NvvOK5W/

反函数如下：p(x) = (x + k + 1) % n，将x = F(n-1, m)，k = (m-1) % n带入
得到F(n, m) = [F(n-1, m) + m] % n 递归表达式

我们这里不用递归代码，使用迭代从下往上计算

注意：迭代过程中，n的取值是动态改变的，并不是直接取“n”

代码

function LastRemaining_Solution(n, m) {
  // write code here
  if (!n) return -1
  let fn = []
  fn[1] = 0
  for (let i = 2; i <= n; i++) {
    fn[i] = (fn[i - 1] + m) % i
  }
  return fn[n]
}