思路1:用数学归纳法推导出递推公式,设有n个人(编号0~(n-1)),从0开始报数,报到(m-1)的退出,剩下的人继续从0开始报数。令f[i]表示i个人时最后胜利者的编号,则有递推公式:
f[1]=0;
f[i]=(f[i-1]+m)%i; (i>1)
https://blog.csdn.net/crazy__chen/article/details/45115911
//递归法int LastRemaining_Solution(int n, int m){if (n <= 0 || m <= 0) return -1;return n == 1 ? 0 : (LastRemaining_Solution(n - 1, m) + m) % n;}//非递归法int LastRemaining_Solution(int n, int m){if (n <= 0 || m <= 0) {return -1;}int ans = 0;for (int i = 2; i <= n; i++) {ans = (ans + m) % i;//注意此处是i}return ans;}
时间:O(N)
思路2:环形链表模拟
