1、题目描述
0,1，...，n-1这n个数字排成一个圆圈，从数字0开始每次从这个圆圈里删除第m个数字，求出这个圆圈里剩下的最后一个数字。
2、解题代码
（1）方法一
利用循环链表模拟这个过程,每找到一个要删除的数字就将其从循环链表里移除，直到找到最后的一个数字
public class LastNumberInCircle_45
{
/************************************************************************
* 解法1：利用循环链表。
* @param n n个数字
* @param m 每次删除第m个数字
* @return 最后剩下的数字
************************************************************************/
public int LastRemaining_Solution(int n, int m)
{
if (n < 1 || m <1)
return -1;
CircleNode head = new CircleNode(0);
CircleNode tail = head;
for (int i = 1; i < n; ++i)
tail = (tail.next = new CircleNode(i));
//形成循环链表
tail.next = head;
while (tail != tail.next)
{
for (int i = 1; i < m; ++i)
tail = tail.next;
//此时tail 是要出列节点的前一个节点
tail.next = tail.next.next;
}
return tail.value;
}
}
class CircleNode
{
int value;
CircleNode next;
public CircleNode(int value)
{
this.value = value;
}
}
（2）方法二
试着找到每次被删除数字有哪些规律。首先定义一个关于n和m的方程f(n,m)，表示在n个数字0,1，...，n-1中每次删除第m个数字最后剩下的数字。
- 在这n个数字中，第一个被删除的数字是(m-1)%n记为k
k = (m-1)%n .......................................A
那么删除k之后剩下的n-1个数字0,1，...k-1，k+1，...，n-1，并且下一次删。除数字从k+1开始计数。相当于在剩下的序列中，k+1排在最前面，从而形成k+1，...，n-1，0,1，...k-1。该序列最后剩下的数字也是关于n和m的函数。由于这个序列的规律和前最初序列不一样，因此函数不同于最初序列，即为f'(n-1, m)。最初序列最后剩下的数字f(n,m)一定是删除一个数字之后的序列最后剩下的数字，即
f(n,m)=f'(n-1, m) .................................B
接下来，定义一个映射p，p(x) = (x-k-1)%n，它表示如果当前的数字是x，那么映射后的数字是(x-k-1)%n。该映射的你映射为p-1(x) = (x+k+1)%n。把剩下的这n-1个数字的序列k+1，...，n-1，0,1，...k-1做一个映射p，得到
k+1 --------------->0
k+2 --------------->1
...
n-1 ---------------->n-k-2
0 ------------------->n-k-1
1 ------------------->n-k
...
k-1 ----------------->n-2
由于映射之后的序列和最初的序列具有相同的形式，即都是从0开始的连续序列，因此仍然可以用函数f表示，记为f(n-1,m),映射之前的序列中最后剩下的数字
f'(n-1, m)=p-1[f(n-1, m)]=[f(n-1, m)+k+1]%n ..................................C
把A、B带入C得
f(n,m)=f'(n-1, m)=[f(n-1, m)+m]%n .................................................D
经过上面分析，得到一个递推公式。要得到n个数字的序列中最后剩下的数字，只需要得到n-1个数字的序列中最后剩下的数字，并以此类推。当n=1时，也就是序列中开始只有一个数字0，那么最后剩下数字也是0。把这种关系表示为
f(n,m) = 0...............................n=1
f(n,m)=[f(n-1, m)+m]%n.........n>1
编码如下
/********************************************************************************
* 解法2：试着找到每次被删除的数字有哪些规律
****************************************************************************/
public int LastRemaining_Solution2(int n, int m)
{
if(n < 1 || m < 1)
return -1;
int last = 0;
for (int i = 2; i <= n; ++i)
last = (last + m) % i;
return last;
}
