题目解析

两种方法的详细过程可参考文章：面试题

方法一：循环数组

• 假设当前索引号为cur，则下一个挑礼物的小朋友索引号为new = cur + m - 1
• 该小朋友不再回到圈内，从他下一个小朋友开始报数，因此他下一个小朋友的索引号为cur = new,即cur = cur + m - 1
• 由于小朋友围成了圈，因此索引号还需对总人数取模，即cur = (cur + m - 1) % n
• 每轮离开一个小朋友，直至只剩下一个小朋友。
• 索引号记为当前剩余小朋友中的位置，编号则是小朋友原始的编号。题目要求输出剩下小朋友的编号，而计算过程是对岁引号进行操作，因此需要先存储每个编号对应的索引号。

代码实现

public int LastRemaining_Solution(int n, int m) {
        if(n == 0){
            return -1;
        }

        int cur = 0;
        ArrayList<Integer> list = new ArrayList<>();
        for(int i = 0;i < n;i++){
            list.add(i);
        }
        while(n > 1){
            cur = (cur + m - 1) % n;
            list.remove(cur);
            n--;
        }
        return list.get(0);
    }

• 时间复杂度：O(n)
• 空间复杂度：O(n)

方法二：递推公式

反向递推。
定义F(n,m)表示最后剩下的小朋友的索引号,题目最终输出索引号对应的编号。推导F(n - 1,m):
以[0,1,2,3,4,5,6,7]为例，n = 8，m = 3，通过计算可知

F(8,3) = 6
F(7,3) = 3
F(6,3) = 0
F(5,3) = 3
F(4,3) = 0
F(3,3) = 1
F(2,3) = 1
F(1,3) = 0

通过反推可得（反推过程参考文章：面试题 ）：

public int LastRemaining_Solution(int n, int m) {
        if(n == 0){
            return -1;
        }

        int f = 0;
        for(int i = 2;i <= n;i++){
            f = (f + m) % i;
        }
        return f;
    }

• 时间复杂度：O(n)
• 空间复杂度：O(1)