题目

Leetcode的第1823题和《剑指offer》的面试题62都是一种类型的问题，即约瑟夫环（Josephuse）问题。两者稍微优点不同，Leetcode的题目是从数字1开始，《剑指offer》的题目是从数字0开始，这个不影响方法，后面以数字1开始进行讲解。

方法一：经典接法，用环形链表模拟圆圈

注意题目的要求是圆圈中，所以我们创建一个共有n个节点的环形链表，然后每次在链表当中删除第m个节点。这种方法可以称作模拟法，就是按照人家的玩法一步步做。

C++有一个顺序容器std::list，可以用来模拟环形链表。但是std::list本身并没有环形结构，所以当迭代器扫描到链表末尾时，就把迭代器移动到链表的头部，这样就人为地生成一个“环形链表”。

class Solution {
public:
    int findTheWinner(int n, int k) {
        list<int> nums;

        //将数据填入链表，这里需要的空间是O（n）
        for (int i = 1; i <= n; ++i) 
            nums.push_back(i);

        auto cur = nums.begin();    //迭代器指向头部
        while (nums.size() > 1) {
            for (int i = 1; i < k; ++i) {
                cur++;                  //迭代器向前移动k-1个人，因为自己也算一个人
                if (cur == nums.end())
                    cur = nums.begin();
            }

            /*准备淘汰第l个人*/
            auto temp = ++cur;          //保留被淘汰人顺时针的下一位，不然待会找不到
            if (temp == nums.end())
                temp = nums.begin();    //每次移动都要特别注意会不会移动到末尾

            --cur;                      //迭代器刚才指向temp了，现在退回来
            nums.erase(cur);            //淘汰
            cur = temp;
        }     
        return *cur;

    }
};

因为每淘汰一个人就需要k次，所以程序的时间效率为O（nm），而程序需要一个长度为n的辅助链表，所以空间效率为O（n）。

易错点

1. 题目明确计数时需要 包含 起始时的那位小伙伴，所以会发现数人时i是从1开始的。比如k=2，代表每数两个人淘汰该小伙伴，cur已经指向了一名小伙伴，只需要再往前数一个就行了，i=1符合这种情况，而i=0则不符合。

for (int i = 1; i < k; ++i) {

2. cur++ 和 ++cur的效果是相同的，但是效率却不同。++cur返回的是引用，cur++返回的是临时对象。临时对象必须要先创建，然后用完再销毁，会增加很多无用的负担。

auto temp = ++cur; 

方法二：数学创意解法

假设f（n, k）表示有n个人玩游戏，淘汰第k个人，最终的胜利者winner。

我们取n = 10, k = 2，即 1 2 3 4 5 6 7 8 9 10(队列A)，所以f（10, 2）即10个人玩游戏最终的胜利者，我们称之为winner1。

找到第二个人，然后淘汰，队伍变成 1 3 4 5 6 7 8 9 10；

因为我们是以淘汰的人的后一位重新开始计数的，所以队伍可以变成 3 4 5 6 7 8 9 10 1。

我们对现在的队伍进行某种关系的映射，
3 -> 1
4 -> 2
5 -> 3
6 -> 4
7 -> 5
8 -> 6
9 -> 7
10 -> 8
1 -> 9

为什么要存在这种的映射，因为这样才能符合f（n,k），从而产生规律。右列的队伍(队列B)最终也会产生一个胜利者，即f（9,2）,我们称之为winner2.

不难发现winner1和winner2对应的就是同一个胜利者，因为队列B其实就是队列A淘汰一个人产生的，可以说是第二轮游戏。

但是他们不能直接等于，因为队列B经过了某种映射，比如winner2 = 5，实际上胜利者不是5号选手，而是映射前的7号选手（见上述队列）。所以我们必须将winner2重新映射回去。

经过观察，右边的数经过运算规则如下：
(主要10->8反映射比较特别。)
如果(x+k) % n == 0， 则原数字 = n；
如果(x+k) % n != n, 则原数字 = (x + k) % n;

所以我们有式子winner1 = (winner2 + k) % n 或 winner1 = n 。

看有一些博客关于约瑟夫问题的介绍，公式会是winner1 = (winner2 + k) % n ，那是因为有些题目是从0开始的，而这里Leetcode题目是以1开始的，稍微有点不同。

观察这条表达式我们可以看到，需要得到 f(10,2) 这个数值必须要知道 f(9,2) ，那同理可得f(9,2)必须要求得f（8， 2），然后一路求下去，通项公式为f(n,k ) = [f(n-1, k) + k] % n 或 f(n,k ) = n。

初始条件为f（1，k）= 1，因为只有一个人玩游戏，胜利者必然是1号选手。代码如下（C++）：

class Solution {
public:
    int findTheWinner(int n, int k) {
       
       if (n==1) return 1;

       int winner = 1;

       for (int i = 2; i <= n; ++i ) {
           winner = winner + k;
           if ((winner % i) == 0)
                winner = i;
            else
                winner = winner % i;

       }
       return winner;

    }
};