约瑟夫环

这个问题是我室友今年在面武汉huawei时候手撕代码的原题。

剑指offer上也有这个题，如果用模拟的方法做确实不算难，但是如果给的数据量过大模拟法就不能过。

数学推导的过程有点复杂，还是老老实实做个记录吧。

问题来源

这个问题是以弗拉维奥·约瑟夫命名的，他是1世纪的一名犹太历史学家。他在自己的日记中写道，他和他的40个战友被罗马军队包围在洞中。他们讨论是自杀还是被俘，最终决定自杀，并以抽签的方式决定谁杀掉谁。约瑟夫斯和另外一个人是最后两个留下的人。约瑟夫斯说服了那个人，他们将向罗马军队投降，不再自杀。约瑟夫斯把他的存活归因于运气或天意，他不知道是哪一个。

一般形式

约瑟夫问题是个有名的问题：N个人围成一圈，从第一个开始报数，第M个将被杀掉，最后剩下一个，其余人都将被杀掉。例如N=6，M=5，被杀掉的顺序是：5，4，6，2，3。

下面我们用一组图来展示上面描述：

LeetCode

leetcode上的剑指offer也有这个问题.

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

0,1,,n-1这n个数字排成一个圆圈，从数字0开始，每次从这个圆圈里删除第m个数字。求出这个圆圈里剩下的最后一个数字。

例如，0、1、2、3、4这5个数字组成一个圆圈，从数字0开始每次删除第3个数字，则删除的前4个数字依次是2、0、4、1，因此最后剩下的数字是3。

示例 1：

> 输入: n = 5, m = 3
> 输出: 3
>

示例 2：

> 输入: n = 10, m = 17
> 输出: 2
>

限制：

• 1 <= n <= 10^5
• 1 <= m <= 10^6

模拟法

思路: 就类似上图，用一个循环链表模拟该过程，如果符合该数就删掉该节点，直到链表的节点数目为1.]

不过时间复杂度为O(n * m)会TLE

class Solution {
public:
    int lastRemaining(int n, int m) {
        // 用链表来模拟
        list<int> list;
        for (int i = 0; i < n; ++i)
            list.push_back(i);
        int cnt = 1;
        auto iter = list.begin();
        while (1) {
            if (list.size() == 1)   break;
            // 当报数报到m时
            if (cnt == m) {
                list.erase(iter++);
                // 删除节点后iter ++ 需要判断是否已经到尾部了
                // 若是则要将其指向开头
                if (iter == list.end()) iter = list.begin();
                cnt = 1;
            }
            else {
                iter++;
                // iter ++后需要判断是否已经到尾部了
                // 若是则要将其指向开头
                if (iter == list.end()) iter = list.begin();
                cnt++;
            }
        }
        return *list.begin();
    }
};

数学法

数学法可以参考这个链接的思路：csdn陈浅墨

class Solution {
public:
    int lastRemaining(int n, int m) {
        // 约瑟夫环的递推公式
        // 数组的下标从0开始
        // 最终数组的下标为0 f(N,M) = (f(N-1,M) + M) %(N)
        // 从倒数第一行向上推,倒数第二行有两个数字, 最开始一行有n个数
        int idx = 0;
        for (int i = 2; i <= n; ++i)
            idx = (idx + m) % i;
        return idx;
    }
};