圆圈中最后剩下的数

题目描述

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

如果没有小朋友，请返回-1

第一想法

• 写个环形表,穷举到最后一个.

AC代码

class Solution {
public:
    int LastRemaining_Solution(int n, int m)
    {
        if(n <= 0)
            return -1;
        else{
            int i = 0;
            Node *head = new Node(0);
            Node *p = head;
            while(++i < n){
                Node *node = new Node(i);
                p -> next = node;
                p = node;
            }
            p -> next = head;
            int k = m;
            while(head -> next != head){
                Node *tmp = head;
                while(--k){
                    p = p -> next;
                    tmp = tmp -> next;
                }
                k = m;
                head = tmp -> next;
                p -> next = head;
                delete tmp;
            }
            return head -> val;
        }
        
    }
    
    struct Node{
        int val;
        struct Node *next;
        Node(int x):
            val(x),next(NULL){

            }
    };
};

速度太慢了

看了讨论区

约瑟夫问题

class Solution {
public:
    int LastRemaining_Solution(int n, int m)
    {
        if(n <= 0)
            return -1;
        else{
            int last = 0;
            for(int i = 2; i <= n; i++){
                last = (last + m) % i;
            }
            return last;
        }
    }
};

约瑟夫问题的通项
f(n,m)=(f(n-1,m)+m)%n