题目描述

编号为1到n的n个人围成一圈。从编号为1的人开始报数，报到m的人离开。
下一个人继续从1开始报数。
n-1轮结束以后，只剩下一个人，问最后留下的这个人编号是多少？

方法一 模拟

解题思路

可以使用循环链表模拟约瑟夫问题。以5个人报数为2的离开为例：

如图所示，每次去掉一个，最后留下的人编号为3。在每次报数时，改变第m个节点前后节点相应的指针以将该节点从链表中删除。

代码示例

class Solution {
public:
    /**
     * 
     * @param n int整型 
     * @param m int整型 
     * @return int整型
     */

    struct Node {
        int val;
        Node* next;
        Node(int _val) : val(_val), next(nullptr) {}
    };

    int ysf(int n, int m) {
        Node* head = new Node(1), *temp = head;
        for (int i = 2; i <= n; ++i) {
            // 构建链表
            Node* node = new Node(i);
            temp->next = node;
            temp = temp->next;
        }

        // 首尾相连构成环
        temp->next = head;
        temp = head;

        // 进行n-1次报数
        for (int i = 0; i < n - 1; ++i) {
            // 每次报数为m
            for (int j = 1; j < m - 1; ++j)
                temp = temp->next;

            // 将第m个节点从链表中删除
            Node* out = temp->next;
            temp->next = temp->next->next;
            temp = temp->next;
            // delete掉这个节点
            delete out;
        }
        // 返回最后一个节点的值
        return temp->val;
    }
};

复杂度分析

• 时间复杂度：进行n-1次报数，每次报数经过m个元素，时间复杂度为
• 空间复杂度：使用环形链表进行模拟，链表长度为n，空间复杂度为

方法二 数学+递归

解题思路

约瑟夫问题的数学解法思路与动态规划类似。将问题答案记为，该值代表n个人报数为m时留下来的编号。现在需要确定与的关系。
对于第一次删除，长度为n的序列的第m%n个元素会被选中。删除之后序列长度为n-1。假设我们已经知道与的值，假设，，经过下图的排列方法之后，应该指向同一个元素。

即：从头开始数位置的元素等于从第一次删除位置数位置的元素。根据此等式关系，结合第一次删除位置为m%n的条件，我们可以得到二者的递推关系。
根据上述递推关系可以得到递推写法。

代码示例

class Solution {
public:
    /**
     * 
     * @param n int整型 
     * @param m int整型 
     * @return int整型
     */

    int f(int n, int m) {
        // 边界情况
        if (n == 1) {
            return 0;
        }
        // 递归关系
        return (m + f(n - 1, m)) % n;
    }

    int ysf(int n, int m) {
        // 计数从1开始
        return f(n, m) + 1;
    }
};

复杂度分析

• 时间复杂度：需要进行n-1次递归，时间复杂度为
• 空间复杂度：递归深度为n-1，需要大小的栈空间

方法二 数学+迭代

解题思路

方法二中的递归可以简化为迭代方法以降低空间复杂度。可以看出，只与相关，所以我们可以从n=1开始，迭代求出的值，关系式仍然为方法二中提出的递归关系。

代码示例

class Solution {
public:
    /**
     * 
     * @param n int整型 
     * @param m int整型 
     * @return int整型
     */

    int ysf(int n, int m) {
        // 初始化f(n,m)=0
        int f = 0;
        // 根据递归关系式求出不同的n对应的f值
        for (int i = 2; i < n + 1; ++i) {
            f = (m + f) % i;
        }
        // 计数从1开始
        return f + 1;
    }
};

复杂度分析

• 时间复杂度：只要n-1次迭代，时间复杂度为
• 空间复杂度：使用常数个变量，空间复杂度为