题目描述

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

方法一（链表模拟）

1.解题思路

将0到n-1这n个数依次加入到链表，每次模拟题目要求，删除指定位置的元素，剩下的那一个即是最后的数字。

2.代码实现

class Solution {
    public int lastRemaining(int n, int m) {
        List<Integer> list=new ArrayList<>();
        for(int i=0;i<n;i++){
            list.add(i);
        }
        int index=0;
        while(list.size()>1){
            index=(index+m-1)%list.size();
            list.remove(index);
        }
        return list.get(0);
    }
}

3.复杂度分析

• 时间复杂度：需要删除n-1个元素，每次删除的时间复杂度为O(n)，所以时间复杂度为O(n²)。
• 空间复杂度：需要额外的O(n)的链表存储元素，所以空间复杂度为O(n)。

方法二（递归）

1.解题思路

• 终止条件：当最后只剩一个元素时，我们知道这个元素的下标是0
• 递推关系：我们可以根据下标值推算出上一次这个剩余元素所在下标，……一直到有n个元素时，这个元素所在下标也是它本身的值。每一层的下标之间是有一个递推关系的，即：fun(n,m)=(fun(n-1,m)+m)%n
• 举例说明：
  比如0、1、2、3、4，当删除一个数字2后，还剩4个数字，分别是3、4、0、1，此时是n-1个元素，3所在下标为0，往前补m(m=3)个元素，分别是0、1、2、3、4、0、1，此时是n个元素的情况，下标3=(0+3)%5，即fun(n,m)=(fun(n-1,m)+m)%n

2.代码实现

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

3.复杂度分析

• 时间复杂度：需要删除n-1个元素，所以时间复杂度为O(n)。
• 空间复杂度：递归栈的深度为n，所以空间复杂度为O(n)。

方法三（迭代）

1.解题思路

按照方法二递归的思路，从后往前倒推即可。

2.代码实现

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

3.复杂度分析

• 时间复杂度：需要删除n-1个元素，所以时间复杂度为O(n)。
• 空间复杂度：需要额外常熟级别的空间，所以空间复杂度为O(1)。

剑指offer全集入口： 请戳这里