题目描述:
0,1,,n-1这n个数字排成一个圆圈,从数字0开始,每次从这个圆圈里删除第m个数字。求出这个圆圈里剩下的最后一个数字。
例如,0、1、2、3、4这5个数字组成一个圆圈,从数字0开始每次删除第3个数字,则删除的前4个数字依次是2、0、4、1,因此最后剩下的数字是3。
示例 1:
输入: n = 5, m = 3
输出: 3
示例 2:
输入: n = 10, m = 17
输出: 2
解法:
1.常规解法:链表
新建一个链表用于存储0-n-1的元素,每次从链表中删除一个元素,直到链表中只剩下一个元素时,返回该元素
第一次删除的元素下标c为(m-1)%n
后面删除元素的下标c为(c+m-1)%当前链表长度
2.数学推导
假设 n 个数字为 n 个人,我们用函数 f(i)表示当前人数为 i 的时候存活的最后一个人的位置,那么f(1) = 0,再推一步,还剩两个的时候,第 m-1个要被剔除,要剔除哪个呢?
现在我们知道的是 ,也就是当只有一个人的时候,被剔除人的下标为 0,它必定是第 m个,逃过了一劫,因为在它之前第 m-1个是被剔除的,所以在倒数第二步,就是在最后一步的基础上加 m,即:
f(2) = f(1) + m
那么这就是有两个人的时候存活的最后一个人的位置,我们只需要利用公式往上推即可,因为可能会超出当前个数 ii 的范围,所以边计算边取模即可,可以得到递推式:
f(i) = (f(i-1)+m)%i
写的时候,n个数字,要剔除 n-1个,循环 n-1次,i从 2开始直到n结束