62. 圆圈中最后剩下的数

题目链接

牛客

力扣

题目描述

让小朋友们围成一个大圈。然后，随机指定一个数 m，让编号为 0 的小朋友开始报数。每次喊到 m-1 的那个小朋友要出列唱首歌，然后可以在礼品箱中任意的挑选礼物，并且不再回到圈中，从他的下一个小朋友开始，继续 0...m-1 报数 .... 这样下去 .... 直到剩下最后一个小朋友，可以不用表演。

解题思路

本题的难点在于递推公式的推导或者说是理解。

• f(n,m) 表示序号为 0,1,...,n-1 的圈要一直淘汰第 m 个人最终剩下来的序号，这里序号和对应的值是一致的。
• f(n-1,m) 表示序号为 0,1,...,n-2 的圈要一直淘汰第 m 个人最终剩下来的序号，这里序号和对应的值是一致的。
• 当我们从 f(n,m) 中第一次淘汰第 m 个人（序号为 (m-1)%n ）时，该序列的长度就变成了 n-1，再淘汰一个第 m 个人时，情况就变成了 f'(n-1,m), 但是此时 f'(n-1,m) 是以 m%n 为序号开始的，而 f(n-1,m) 是以 0 为序号开始的。要想将 f(n-1,m) 对应的索引转换成 f(n,m) 对应的索引/值，则 f(n,m) = (m%n +f(n-1,m) ) % n = (m+f(n-1,m)) % n

func lastRemaining(n int, m int) int {
  if n == 1{return 0}
  return (m + lastRemaining(n-1,m)) % n
}