剑指 Offer 62. 圆圈中最后剩下的数字

剑指 Offer 62. 圆圈中最后剩下的数字

解题思路1：模拟

我们可以使用队列这种数据结构模拟圆环删除节点的过程

算法流程：

1. 初始化队列，将 0…n-1 入队
2. 初始化计数器 counter，初始值为 1
3. 模拟圆环删除
   1. 当队列大小不等于 1 的时候，循环执行删除节点操作
   2. counter != m 时，将队首元素出队放入队尾，counter++
   3. counter ==m 时，将队首元素删除，counter 恢复初始值 1

代码

class Solution {
    public int lastRemaining(int n, int m) {
        Queue<Integer> queue = new LinkedList<>();
        for(int i = 0; i < n; i++){
            queue.offer(i);
        }
        int counter = 1;
        while(queue.size() != 1){
            if(counter != m){
                queue.offer(queue.poll());
                counter++;
            }else {
                queue.poll();
                counter = 1;
            }
        }
        return queue.poll();
    }
}

复杂度分析

• 时间复杂度：O(NM)

我们每次都要遍历 M 个元素，并且这个过程要执行 N-1 次，时间复杂度为 O(NM)

• 空间复杂度：O(N)

我们额外使用了队列，队列占用了 O(N) 的额外空间

解题思路2：数学

本题实际上是一道非常著名的数学问题：约瑟夫环问题；经过数学推导，我们可以使用动态规划来解决。

定义在 n 个数字中不断删除第 m 个数字为 「n, m」问题， 为「n, m」问题的结果，即：在 n 个数字（序列 0 ~ n-1）中不断删除第 m 个数字后，最后剩下的数字。

那么， 就是「n-1, m」问题的结果，即：在 n-1 个数字（序列 0 ~ n-2）中不断删除第 m 个数字后，最后剩下的数字。

对于 n 个数字的序列，首轮删除环中的第 m 个数字之后，我们会得到一个长度为 n-1 的序列

删除的数字为 m-1，但是我们要考虑到 m 有可能大于 n ，所以，删除的数字应该表示为：(m-1) % n；删除该数字后，环会从删除后的数字的下一个数字（m % n）开始，设 x = m % n

可以得到「n, m」首轮删除第 m 个元素之后的序列为：

x，x+1，x+2，… 0，1，2，x-3，x-2

「n-1, m」的序列为：

0，1，2，…n-3，n-2

所以，我们可以得到「n, m」与 「n-1, m」的递推关系式：

进而推断：

动态规划的解题步骤：

• 状态定义
• 确定状态转移方程与初始值
• 递推实现

题目中给定，n ≥ 1 ；所以我们可以确定方程初始值：

确定了状态转移方程与初始值，我们可以使用递归或动态规划来解决本问题

代码

Recursion

class Solution {
    public int lastRemaining(int n, int m) {
        // f(n) = (f(n - 1) + m) % n
        // f(1) = 0
        if(n == 1){
            return 0;
        }
        return (lastRemaining(n - 1,m) + m) % n;
    }
}

DP

class Solution {
    public int lastRemaining(int n, int m) {
        // f(n) = (f(n - 1) + m) % n
        // f(1) = 0
        int res = 0;
        for(int i = 2; i <= n; i++){
            res = (res + m) % i;
        }
        return res;
    }
}

复杂度分析

Recursion

• 时间复杂度：O(N)

• 空间复杂度：O(N)

递归深度为 O(N)

DP

• 时间复杂度：O(N)

• 空间复杂度：O(1)

原地 DP，我们只使用了有限的几个变量，额外空间占用 O(1)