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