题目描述

有个游戏是这样的：⾸先，让 n 个⼩朋友们围成⼀个⼤圈，⼩朋友们的编号是0~n-1。然后，随机指定⼀个数 m，让编号为0的⼩朋友开始报数。每次喊到 m-1 的那个⼩朋友要出列唱⾸歌，然后可以在礼品箱中任意的挑选礼物，并且不再回到圈中，从他的下⼀个⼩朋友开始，继续 0… m-1报数….这样下去….直到剩下最后⼀个⼩朋友，可以不⽤表演，并且拿到⽜客礼品，请你试着想下，哪个⼩朋友会得到这份礼品呢？

示例 输⼊：5,3 输出：2

思路及解答

数组模拟

通过布尔数组标记小朋友的出局状态

  • 时间复杂度：O(n×m)，最坏情况下每个小朋友都需要报数m次

  • 空间复杂度：O(n)，需要长度为n的布尔数组

循环链表

使用循环链表模拟小朋友围成的圈，将小朋友存入链表，循环删除第m个元素

  • 时间复杂度：O(n×m)，需要遍历链表进行删除操作

  • 空间复杂度：O(n)，需要存储n个节点

数学归纳法（推荐）

分析每次被删除的数字规律，直接计算出最后的数字，不需要模拟

递推公式的推导过程：

  1. 第一次删除：从0开始报数，删除第(m-1)%n个小朋友

  2. 重新编号：删除后，从第m%n个小朋友开始重新编号：

  • 旧编号：m%n, m%n+1, …, n-1, 0, 1, …, m%n-1

  • 新编号：0, 1, 2, …, n-2

  1. 映射关系：新编号x对应的旧编号为(x + m) % n

示例验证（n=5, m=3）：

  • 时间复杂度：O(n)，需要n次递归调用

  • 空间复杂度：O(n)，递归调用栈深度

迭代优化

将递归转为迭代，避免栈溢出风险，是生产环境的最佳选择

  • 时间复杂度：O(n)，只需一次循环

  • 空间复杂度：O(1)，只使用常数空间