题目描述

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

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

• 这其实就是一道经典的约瑟夫环
• 约瑟夫环问题：据说著名犹太历史学家 Josephus有过以下的故事：在罗马人占领乔塔帕特后，39 个犹太人与Josephus及他的朋友躲到一个洞中，39个犹太人决定宁愿死也不要被敌人抓到，于是决定了一个自杀方式，41个人排成一个圆圈，由第1个人开始报数，每报数到第3人该人就必须自杀，然后再由下一个重新报数，直到所有人都自杀身亡为止。然而Josephus 和他的朋友并不想遵从。首先从一个人开始，越过k-2个人（因为第一个人已经被越过），并杀掉第k个人。接着，再越过k-1个人，并杀掉第k个人。这个过程沿着圆圈一直进行，直到最终只剩下一个人留下，这个人就可以继续活着。问题是，给定了和，一开始要站在什么地方才能避免被处决？Josephus要他的朋友先假装遵从，他将朋友与自己安排在第16个与第31个位置，于是逃过了这场死亡游戏。

样例1

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

样例2

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

算法1

(循环链表) $O(n^2)$

每次找到需要删除的节点，并删除该节点。
假设每次数组开始的节点下标为k，则每次删除下标$(k+m-1)mod(n)$号节点
一共删除$n-1$个节点，每删除一个节点需要遍历链表，所以总时间约为$O(n^2)$
这种做法会超时，不推荐使用

时间复杂度 $O(n^2)$

算法2

(逆推法)

拿$n=5,m=3$为例模拟删除过程，用首尾拼接的方式表示循环数组

第一轮：0 1 2 3 4 0 1 2 3 4，删除2，此时3的下标为(0 + 3) % 5 = 3
第二轮：3 4 0 1 3 4 0 1，删除0，此时3的下标为(1 + 3) % 4 = 0
第三轮：1 3 4 1 3 4，删除4，此时3的下标为(1 + 3) % 3 = 1
第四轮：1 3 1 3，删除1，此时3的下标为(0 + 3) % 2 = 1
第五轮：3，此时3的下标为0

• 因为每轮循环都以被删除的节点的下一个节点作为头节点，所以从一轮循环到下一轮循环就相当于把所有节点的下标往前移动3个单位，反过来就是从一轮循环推导前一轮就相当于把所有节点的下标往后移动3个单位，所以可以通过安全的节点最后的下标依次推导出刚开始的下标
• 注意：为了避免越界，每次求下标都需要$mod$上一轮数组的长度

时间复杂度 $O(n)$

Java 代码

    public int lastRemaining(int n, int m) {
        int res = 0;
        for (int i = 2; i <= n; i++){
            res = (res + m) % i;
        }
        return res;
    }