跟着姚桑学算法-圆圈中最后剩下的数字

题. 圆圈中最后剩下的数字

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

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

数据范围
1≤n,m≤4000

样例

输入：n=5 , m=3

输出：3

【题解】--- 链表模拟

本题就是有名的约瑟夫环问题。我们可以环形列表来模拟，每次从这个列表中删除第m个元素，一直到列表最后剩下一个元素为止。

考虑用STL中std::list来模拟这个环形列表，由于list并不是一个环形的结构，因此每次跌代器扫描到列表末尾的时候，要记得把跌代器移到列表的头部。

这样就是按照一个圆圈的顺序来遍历这个列表了。

由于我们需要一个有n个结点的环形列表来模拟这个删除的过程，因此内存开销为O(n)。

而且这种方法每删除一个数字需要m步运算，总共有n个数字，因此总的时间复杂度是O(mn)。

复杂度分析：

时间复杂度为O(mn)。

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);
        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);//删除第m个元素
            if (it == nums.end()) it = nums.begin();
            k = m - 1;
        }
        return nums.front();
    }
};