【算法狂想曲】约瑟夫环 递推 模板

2020-03-30   101 次阅读


飞行堡垒坠机了,拿去维修点修理,今天用上了大一的老电脑,将就着点用,环境没有,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.

知识共享署名-非商业性使用-相同方式共享 4.0 国际许可协议