题目：圆圈中最后剩下的数字

0,1,···,n-1这n个数字排成一个圆圈，从数字0开始，每次从这个圆圈里删除第m个数字（删除后从下一个数字开始计数）。求出这个圆圈里剩下的最后一个数字。

例如，0、1、2、3、4这5个数字组成一个圆圈，从数字0开始每次删除第3个数字，则删除的前4个数字依次是2、0、4、1，因此最后剩下的数字是3。

示例 1：

输入: n = 5, m = 3
输出: 3

示例 2：

输入: n = 10, m = 17
输出: 2

限制：

• 1 <= n <= 10^5
• 1 <= m <= 10^6

---

Discussion | Solution

方法一：循环列表

分析：采用链表模拟圆圈，当圆圈前后指针为自身时，结束。

    typedef struct number
    {
        int val;
        struct number* pre;
        struct number* next;
    }number;
    
    //创建圆圈，返回头结点
    number* createCircle(int n){
        int i = n;
        number *hp, *fp = nullptr, *pre = nullptr, *tail;
 
        while (i >= 0)
        {
            hp = (number*)malloc(sizeof(number) * 1);
            if(hp ){
                //节点赋值
                hp->val = i;
                hp->next = fp;
                //前一个节点的pre为当前节点
                if(fp) fp->pre = hp;
                // cout << hp->val << endl;
                if(n == i)  tail = hp;
                
                fp = hp;
                i--;
            }
        }
        tail->next = hp;
        hp->pre = tail;
        return hp;
    }
 
    //计算最后一个值, 每次删除第n个值
    int retLastNumber(number* root, int n, int m){
        int size = n;
        if(!root) return -1;
        number* step = root, *temp;
        while(step->pre != step){
            //遍历
            int times = m%size == 0 ?  m: m%size;
            for(int i = 1; i < times; i++){
                step = step->next;
            }
 
            //删除
            temp = step;
            temp->pre->next = temp->next;
            temp->next->pre = temp->pre;
            step = temp->next;
 
            free(temp);
            size--;
        }
        cout << "==" <<  step->val;
        return step->val;
    }
    
int lastRemaining(int n, int m) {
      number* root = createCircle(n-1);
      return retLastNumber(root, n, m);
}

方法二：数组模拟

分析：采用vector数据，循环至size==1

    int getResult(int n, int m){
        int size = n, pos = 0;
        vector<int> list;
 
        for(int i=0; i < n; i++)
            list.push_back(i);
        
        while (size > 1)
        {    
            pos = (pos + m-1) % size;
            list.erase(list.begin() + pos);
            size--;
        }
        return *list.begin();
    }
 
    int lastRemaining(int n, int m) {
       return getResult(n,m);
    }

方法三：约瑟夫环

数学方法：约瑟夫环

    //数学问题：约瑟夫环
    int getAnsInMath(int n, int m){
        if(n == 1) return 0;
        //ans : 胜利者的位置
        int ans = 0;
        for(int size = 2; size <= n; size++){
            ans = (ans + m) %  size;
        }
        return ans;
    }
 
    int lastRemaining(int n, int m) {
       return getAnsInMath(n,m);
    }

Accepted

• 36/36 cases passed (4 ms)
• Your runtime beats 93.34 % of cpp submissions
• Your memory usage beats 80.45 % of cpp submissions (5.7 MB)

总结：常规想到的方法是方法一和方法二，方法三一般现场推倒，不易推倒出；但是方法一和方法二不满足时间要求。