[剑指offer] 46. 孩子们的游戏(圆圈中最后剩下的数)

题目描述

随机指定一个数m,让编号为0的小朋友开始报数。每次喊到m-1的那个小朋友要出列,并且不再回到圈中,从他的下一个小朋友开始,继续0...m-1报数....这样下去....直到剩下最后一个小朋友,求最后剩下哪个人。(注：小朋友的编号是从0到n-1)

---

思路一：

模拟

class Solution
{
  public:
    int LastRemaining_Solution(int n, int m)
    {
        if (n < 1 || m < 1)
            return -1;
        vector<int> arr(n, 0);
        int count = 0;
        int i = -1;
        int step = 0;
        while (count < n)
        {
            i++;
            if (i >= n)
                i = 0;
            if (arr[i] == -1)
                continue;
            step++;
            if (step == m)
            {
                arr[i] = -1;
                step = 0;
                count++;
            }
        }
        return i;
    }
};