LeetCode 剑指 Offer 62. 圆圈中最后剩下的数字

Categories:

题目描述
思路分析
1. 解法一：约瑟夫问题数学递推（推荐）
2. 解法二：递归
相似题目

题目描述

✅ 剑指 Offer 62. 圆圈中最后剩下的数字

思路分析

解法一：约瑟夫问题数学递推（推荐）

核心思路：

经典约瑟夫问题（Josephus Problem）。n 个人围成圆圈，每次数到第 m 个人出列，求最终剩下的人的编号。

递推公式推导：

设 f(n, m) 为 n 个人、每次数 m 个时，最终存活者的下标（0-indexed）。

边界条件：f(1, m) = 0，只有 1 人时，下标为 0。

递推关系：f(n, m) = (f(n-1, m) + m) % n

递推关系推导过程：

当有 n 个人时，第一轮删除编号为 (m-1) % n 的人。删除后剩余 n-1 个人，其编号从 m % n 开始重新排列为 0, 1, 2, …, n-2。子问题 f(n-1, m) 给出的是在新编号体系下的答案，将新编号映射回原编号即得递推公式：原编号 = (f(n-1, m) + m) % n。

从 f(1, m) = 0 迭代到 f(n, m) 即可得到最终答案（原编号即为题目所求的数字，因为 0-indexed 与实际数字一致）。

复杂度分析：

时间复杂度：O(n)，其中 n 为人数，需要从 1 迭代到 n。

空间复杂度：O(1)，只使用常数额外空间（迭代方式）。

Java 实现

class Solution {
    public int lastRemaining(int n, int m) {
        // 从 f(1, m) = 0 开始，迭代递推到 f(n, m)
        int pos = 0;
        for (int i = 2; i <= n; i++) {
            // 约瑟夫递推：f(i, m) = (f(i-1, m) + m) % i
            pos = (pos + m) % i;
        }
        return pos;
    }
}

Go 实现

func lastRemaining(n int, m int) int {
    // 从 f(1, m) = 0 开始，迭代递推到 f(n, m)
    pos := 0
    for i := 2; i <= n; i++ {
        // 约瑟夫递推：f(i, m) = (f(i-1, m) + m) % i
        pos = (pos + m) % i
    }
    return pos
}

解法二：递归

核心思路：

与迭代版本逻辑相同，直接使用递归表达约瑟夫公式：

f(1, m) = 0

f(n, m) = (f(n-1, m) + m) % n

递归深度为 n，当 n 较大时有栈溢出风险，不推荐用于大数据量场景。

复杂度分析：

时间复杂度：O(n)，其中 n 为人数，递归深度为 n。

空间复杂度：O(n)，其中 n 为递归调用栈的深度。

Java 实现

class Solution {
    public int lastRemaining(int n, int m) {
        // 递归终止条件：只剩 1 人时，下标为 0
        if (n == 1) {
            return 0;
        }
        // 约瑟夫递推公式
        return (lastRemaining(n - 1, m) + m) % n;
    }
}

Go 实现

func lastRemaining(n int, m int) int {
    // 递归终止条件：只剩 1 人时，下标为 0
    if n == 1 {
        return 0
    }
    // 约瑟夫递推公式
    return (lastRemaining(n-1, m) + m) % n
}

相似题目

题目	难度	考察点
1823. 找出游戏的获胜者	中等	约瑟夫环 / 数学递推
390. 消除游戏	中等	数学 / 递推规律
292. Nim 游戏	简单	数学 / 博弈规律
剑指 Offer 10- I. 斐波那契数列	简单	动态规划 / 数学递推
400. 第 N 位数字	中等	数学规律
打家劫舍	中等	动态规划 / 线性递推

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2026/40284870