题目描述

0,1,…,n−1 这 n 个数字 (n>0) 排成一个圆圈，从数字 0 开始每次从这个圆圈里删除第 m 个数字。

求出这个圆圈里剩下的最后一个数字。

经典约瑟夫环问题

样例

输入：n=5 , m=3

输出：3

算法 1

(模拟环形链表) $O(nm)$

用 $list$ 模拟环形链表，由于 $list$ 不是环形结构，所以当迭代器走到链表末尾时，需要让其转到链表头部形成环

每次从迭代器指向的数开始数，数 $m$ 次找到第 $m$ 个数，将其删除，接着再从下一个位置开始数，循环此过程，直到环中只剩下一个数，就是答案

时间复杂度

环中总共有 $n$ 个数字，需要删掉 $n - 1$ 个数才能得到答案，每删除一个数需要迭代器移动 $m - 1$ 次，所以时间复杂度为 $O(nm)$

参考文献

https://www.acwing.com/solution/content/796/

C++ 代码

#include <list>
class Solution {
public:
    int lastRemaining(int n, int m){
        list<int> nums;
        for (int i = 0; i < n; i ++ ) nums.push_back(i);

        // 从头开始报数，除去当前数外，还需循环 m - 1 次找到第 m 个数
        auto it = nums.begin();
        int k = m - 1;
        while (nums.size() > 1)
        {
            while (k -- )
            {
                it ++ ;
                // 如果迭代器走到末尾将其移到开头继续寻找，形成环形链表
                if (it == nums.end()) it = nums.begin();
            }
            // 删除当前迭代器指定位置上的元素，返回下一个位置的迭代器
            it = nums.erase(it);
            if (it == nums.end()) it = nums.begin();
            k = m - 1;
        }
        return nums.front();        
    }
};

算法 2

(推导递推式) $O(n^2)$

首先我们应该知道 $f[i, m]$ 的含义是 $i$ 个数字中删除第 $m$ 个数字

$f(n, m)$ 表示 $n$ 个数字删除第 $m$ 个数字，删除 $m - 1$，此时圆中的数字为 $(0, 1, 2, … m - 2, m, m + 1 .. n - 1)$ (m - 1 被删掉了)
$f(n - 1, m)$ 表示 $n - 1$ 个数字中删除第 $m$ 个数字，开始数数前此时圆中的数字为 $(m, m + 1, m + 2 … n - 1, n[0], n + 1[1], n + 2[2]…) % n$
观察两组数字，可得递推式：f(n, m) = (f(n - 1, m) + m) % n

边界：当 n = 1 时圆中只有一个数字 $0$，返回 $0$ 即可

时间复杂度

由 $f[1, m] = 0$ 递推 $n - 1$ 次就可以得到 $f[n, m]$，所以时间复杂度为 $O(n)$

C++ 代码

class Solution {
public:
    int lastRemaining(int n, int m){
        if (n == 1) return 0;
        return (lastRemaining(n - 1, m) + m) % n;
    }
};