题目描述
题目：0, 1， ···， n-1 共n个数字排成圆圈，从数字0 开始每次从这个圈中删除第m个数字。求这个圆圈中最后剩下的数字。
基础解题思路
时间复杂度o(n)，空间复杂度o(1)
设f(n为初始有n人時最後一個剩余的人的编号，那么有如下递归关系： f(n) = (f(n-1) + m) mod n递归关系的推导：
在n个数字中，第一个被删除的数字为(m-1) mod n，并将其记为k，那么剩余数字为0, 1, ···,k-1, ···，k+1,···, n-1。下一次删除从k+1 开始计数，这样的映射关系定义为p(x)=(x-k-1) mod n,例如k+1→0。相应的该映射的逆映射为p-1(x)=(x+k+1) mod n。关系可以表示为f(n) = 0, n=1, f(n) = [f(n-1) + m] mod n, n > 1。
Java实现
public class Solution {
public int LastRemaining_Solution(
int n,
int m) {
if(n==
0)
return -
1;
int s=
0;
for(
int i=
2;i<=n;i++){
s=(s+m)%i;
}
return s;
}
}
高级解题思路
时间O(log n)，空间O(log n)
1.
