62.孩子们的游戏(圆圈中最后剩下的数).md

62.孩子们的游戏(圆圈中最后剩下的数)

题目描述

有个游戏是这样的：首先，让 n 个小朋友们围成一个大圈，小朋友们的编号是0~n-1。然后，随机指定一个数 m ，让编号为0的小朋友开始报数。每次喊到 m-1 的那个小朋友要出列唱首歌，然后可以在礼品箱中任意的挑选礼物，并且不再回到圈中，从他的下一个小朋友开始，继续 0... m-1报数....这样下去....直到剩下最后一个小朋友，可以不用表演，并且拿到牛客礼品，请你试着想下，哪个小朋友会得到这份礼品呢？

示例

输入

5,3

输出

2

思路 & 解答

这道题，由于是围成一个圆圈，涉及到不断删除儿童（出圈）的问题，所以用链表比较适合。判断如果n，或者m小于等于0，非法情况直接返回-1。

先把0到n-1添加到list中，初始化计数器count为-1，索引位置为-1，返回的元素值为0，循环下面的计数，直到元素全部被删除。

为什么全部删除？这样我们可以直接取最后一个出圈的，也是最后一个待在圈子里面的。

每次计数器和索引位置都加1，然后索引位置如果超过了当前剩下的人数，就需要将索引index设置到开头位置。如果计数刚好等于m-1，那么就移除该索引的元素，并且保存被移除的元素值。同时将计数器count设置为-1，将索引位置退一位，因为已经把当前位置删除了。

代码实现如下：

import java.util.ArrayList;
import java.util.List;

public class Solution {
    public static void main(String[] args) {
        Solution46 solution46 = new Solution46();
        System.out.println(solution46.LastRemaining_Solution(5,3));
    }
    public int LastRemaining_Solution(int n, int m) {
        if(n<=0||m<=0){
            return -1;
        }
        List<Integer> list = new ArrayList<>();
        for(int i = 0;i<n;i++){
            list.add(i);
        }
        int count = -1;
        int index = -1;
        int result = 0;
        while(!list.isEmpty()){
            count++;
            index++;
            if(index>=list.size()){
                index=0;
            }
            if(count==m-1){
                result = list.remove(index);
                count=-1;
                index--;
            }
        }
        return result;
    }
}

C++ 代码如下：

class Solution {
public:
    int LastRemaining_Solution(int n, int m) {
        if (n <= 0 || m <= 0) {
            return -1;
        }
        vector<int> list;
        for (int i = 0; i < n; i++) {
            list.push_back(i);
        }
        int count = -1;
        int index = -1;
        int result = 0;
        while (list.size() > 0) {
            count++;
            index++;
            if (index >= list.size()) {
                index = 0;
            }
            if (count == m - 1) {
                result = list[index];
                list.erase(list.begin() + index);
                count = -1;
                index--;
            }
        }
        return result;
    }
};

上面的做法，时间复杂度是O(N^2), 每次删除一个节点，需要先找到那个节点，然后再删除，查找的时间复杂度为O(N),空间上，借助了一个队列，空间复杂度是O(N)。

第二种方法，是根据数学归纳法，分析每次被删除的数字规律，直接计算出最后的数字，不需要模拟：

F(N,M) = ( F(N−1,M) + M ) % N

代码实现：

public class Solution {

    public int LastRemaining_Solution(int n, int m) {
        if (n <= 0 || m <= 0) {
            return -1;
        }
        int result = 0;
        for (int i = 2; i <= n; i++) {
            result = (result + m) % n;
        }
        return result;
    }
}

C++ 代码如下：

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