面试题62:圆圈中最后剩下的数字

题目

0,1，.......，n-1这n个数字排成一个圆圈，从数字0开始，每次从这个圆圈里删除第m个数字。求出这个圆圈里剩下的最后一个数字。
例子:如图所示圆圈，从数字0开始每次删除第3个数字，则删除的前4个数字依次是2,0,4,1，因此最后剩下的数字是3.

image.png

解题思路

• 用环形链表模拟圆圈的经典解法

1. 创建一个共有n个节点的环形链表，每次在这个链表中删除第m个节点。
2. 采用模板库中的list来模拟环形链表。每当迭代器扫描到链表末尾的时候，把迭代器移到链表的头部，就相当于按照顺序在一个圆圈里遍历。

• 创新解法
  定义一个关于n和m的方程f(n,m)，表示每次在n个数字0,1，...,n-1中删除第m个数字最后剩下的数字。
  image.png

代码

• 环形链表

1. 在找第m个节点时，要注意判断节点是否遍历到末尾，若节点遍历到末尾记得把迭代器移到链表的的头部。

2. 找到要删除的第m个节点时，要标记删除结点的下一个节点即next结点，这样，删除第m个节点后，才能继续在链表中遍历下去。

class Solution{
    public:
        int lastRemain(int n,int m)
        {
            if(n<1 || m<1)
            {
                return -1;
            }
            list<int> circle;
            for(int i = 0;i<n;i++)
            {
                circle.push_back(i);
            }

            list<int>::iterator current = circle.begin();
            list<int>::iterator next;
            while(circle.size()>1)
            {
                for(int k=1;k<m;k++)
                {
                    current++;
                    if(current == circle.end())
                    {
                        current = circle.begin();
                    }
                }
                current++;
                next = current;
                if(next == circle.end())
                {
                    next = circle.begin();
                }
                current--;
                circle.erase(current);
                current = next;
            }
            return *current;
        }
}

• 创新解法

class Solution{
    public:
        int lastRemain_2(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;
        }
};

完整代码见GitHub