圆圈中最后剩下的数字

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;
    }