[題記-數學-面試題]約瑟夫環-leetcode

題目：圓圈中最後剩下的數字

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

經典約瑟夫問題：

第一個想法便是迴圈鏈表，走起：

代碼（c++）：

class Solution {
public:
    int lastRemaining(int n, int m) {
        list<int> l;
        for ( int i = 0; i < n; i++ ) l.push_back(i);
        
        int num = 0;
        int coor = 0;
        while ( l.size() > 1 ) {
            if( num == m - 1 ) {
                list<int>::iterator t = l.begin();
                advance(t,coor);
                l.erase( t );
                num = 0;
            }
            else {
                num++;
                coor = ( coor + 1 ) % l.size();
            }
        }
        return l.back();
    }
};

非常順利的超時了。。。

於是求助評論大佬，發現還有數學解法：

最終剩下一個人時的安全位置肯定為0，反推安全位置在人數為n時的編號
人數為1： 0
人數為2： (0+m) % 2
人數為3： ((0+m) % 2 + m) % 3
人數為4： (((0+m) % 2 + m) % 3 + m) % 4

得出代碼(c++)：

class Solution {
public:
    int lastRemaining(int n, int m) {
        int p = 0;
        for ( int i = 2; i <= n; i++ ) {
            p = ( p + m ) % i;
        }
        return p;
    }
};

2020-03-30-22:29:48