圆圈中最后剩下的数字

题目描述

每年六一儿童节,牛客都会准备一些小礼物去看望孤儿院的小朋友,今年亦是如此。 HF作为牛客的资深元老,自然也准备了一些小游戏。其中,有个游戏是这样的: 首先,让小朋友们围成一个大圈。然后,他随机指定一个数m,让编号为0的小朋友开始报数。每次喊到m-1的那个小朋友要出列唱首歌,然后可以在礼品箱中任意的挑选礼物,并且不再回到圈中,从他的下一个小朋友开始, 继续0…m-1报数….这样下去….直到剩下最后一个小朋友,可以不用表演,并且拿到牛客名贵的“名侦探柯南”典藏版(名额有限哦!!^_^)。请你试着想下,哪个小朋友会得到这份礼品呢？(注：小朋友的编号是从0到n-1)

解法一

使用循环链表来存数据（或者使用数组，单向链表模拟循环链表），直接的解法；不过用数组模拟的话需要存储是否被移除的信息，并且在寻找下一个未移除点的时候要遍历很多已经移除的点，时间效率低；用链表直接删除就不会有这个问题，不过要多一些删除构建链表的操作；

代码

//使用数组实现
int LastRemaining_Solution(int n, int m){
               if(n<1||m<1) return -1;
        
        int *ring = new int[n];
        for(int i = 0 ; i < n;i++){
            ring[i] = 0;
        }
        int res = n;
        int index = 0;
        int count = 1;
        while(res!=1){
            if(count!=m){
                index = (index+1)%n;
                while(ring[index]==1) index = (index+1)%n;
                count++;
            }else{
                count = 1;
                ring[index] = 1;
                res--;
                while(ring[index]==1) index = (index+1)%n;
            }
        }
        return index;

}

解法二

剑指offer中的公式推导，最后结果为 ==f(n,m) = [f(n-1，m)+m]%n(n>1); 0(n=1);==

    int LastRemaining_Solution(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;
    }