剑指Offer62 圆圈中最后剩下的数字

链接: https://leetcode-cn.com/problems/yuan-quan-zhong-zui-hou-sheng-xia-de-shu-zi-lcof/

题意

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

解法

约瑟夫问题
听说很久了，一直没有仔细理解过
给每个人一个编号（索引值），每个人用字母代替
下面这个例子是N=8 m=3的例子
我们定义F(n,m)表示最后剩下那个人的索引号，只需要关心最后剩下来这个人的索引号的变化情况即可
每次进行的操作是，去掉第m个人，并把第m+1个人当作新的起点，进行下一次过程

通过最终活着的人反推，考虑人数由8个人变为7个人的过程，如何把7人恢复成8人
首先要将被杀的C恢复到末尾，再右移m位，溢出的部分放到开头
这样就恢复了8个人的状态

图源自换个角度举例解决约瑟夫环
因此我们可以推出递推公式$f(8,3) = [f(7, 3) + 3] \% 8$
进行推广，即$f(n,m) = [f(n-1, m) + m] \% n$

代码

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