飞行堡垒坠机了，拿去维修点修理，今天用上了大一的老电脑，将就着点用，环境没有，IDE没有，只能在线刷刷题维持点生活这样子
刚刚在LeetCode做日常更新题
是一题看起来很简单的题 面试题62 圆圈中剩下的数字(简单)

题目描述如下

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

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

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/yuan-quan-zhong-zui-hou-sheng-xia-de-shu-zi-lcof
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

本菜鸡第一个想到的当然是数据结构打上去直接操作，，
就开了一个vector，然后设置一个索引，动态更新，删除指定位置的数据，最后直接输出最后一个元素即可
这个方法对大部分数据是可行的，但是很遗憾（意料之中）超时了
通过数据28/26
原始菜鸡代码如下

#include<vector>
class Solution {
public:

    int lastRemaining(int n, int m) {
        vector<int> num;
        int indexA=0;
        if(n==0)
        return -1;
        for(int i=0;i<n;i++)
            num.push_back(i);
       
        while(num.size()>1)
        {
            indexA=(indexA+m-1)%(num.size());
             vector<int>::iterator it = num.begin()+(indexA);
            num.erase(it);
        }
        return num[0];
    }

};

这种方法固然可行，但是仔细研究后发现这种方法显然是在时间复杂度上出幺蛾子，因为实在想不出方法于是点进了评论，评论有个传送门指向一个csdn的博客，于是点进去看了看

------------- 原创部分到此结束，接下来都是听课笔记 -------------

首先声明一下，这是听课笔记，原内容为CSDN博主「陈浅墨」的原创文章，遵循 CC 4.0 BY-SA 版权协议
原文链接：
CSDN 约瑟夫环超详细解释

一进入就发现该算法应对的情况正好是围成1圈，每次往下数n个数移除，找出最后留存的数的情况，马上明白这题通过率高以及简单n难度的原因了，这简直是妥妥的模板题（对于老油条来说）

解决方案中第一段是介绍普通解法，我寻思这不是我吗
利用传统数据结构做法时间复杂度高达O(nm)
当n,m非常大的时候，几乎没有办法在短时间内出结果

公式法

我去原来有公式，那这明显比循环删除那种蠢驴做法好多了，直接递推出结果

问题

N个人编号为1，2，……，N，依次报数，每报到M时，杀掉那个人，求最后胜利者的编号。

递推公式

f(N,M)=(f(N−1,M)+M)%N

• f(N,M)表示N个人报数，每报到M时杀掉，最终胜利者的编号
• f(N−1,M)表示N-1个人报数，每报到M时杀掉，最终胜利者的编号

f(1,3)：只有1个人了，那个人就是获胜者，他的下标位置是0
f(2,3)=(f(1,3)+3)%2=3%2=1 f(2,3)=(f(1,3)+3)\%2=3\%2=1f(2,3)=(f(1,3)+3)%2=3%2=1：在有2个人的时候，胜利者的下标位置为1
f(3,3)=(f(2,3)+3)%3=4%3=1 f(3,3)=(f(2,3)+3)\%3=4\%3=1f(3,3)=(f(2,3)+3)%3=4%3=1：在有3个人的时候，胜利者的下标位置为1
f(4,3)=(f(3,3)+3)%4=4%4=0 f(4,3)=(f(3,3)+3)\%4=4\%4=0f(4,3)=(f(3,3)+3)%4=4%4=0：在有4个人的时候，胜利者的下标位置为0
……
f(11,3)=6 f(11,3)=6f(11,3)=6

模板

int cir(int n,int m)
{
	int p=0;
	for(int i=2;i<=n;i++)
	{
		p=(p+m)%i;
	}
	return p;
}

个人理解

每杀掉一个人，其实就是把数组向前移动了M位，然后反过来，就可以得到递推式

结论

太妙了，太强了， 如果大佬就是那个幸存者，那我就是被杀掉的人

Q.E.D.