剑指offer62 圆圈中最后剩余的数字

解法1 模拟法

存在问题

1. 超时
2. 每次循环遍历时,还要遍历已删除的,时间复杂度 大于 m*n

    //2.圆圈最后一个数字
    public int lastRemaining(int n, int m) {
        int[] isDelete =new int[n];
        int p=-1; // 初始指向上一次删除的数字
        int step=0;// 步长
        for (int i = 0; i <n ; i++) { // 删除所有数字,最后删除的就是最后剩余的
            while (step<m){
                p+=1;
                p=p%n;
                if (isDelete[p]==0){
                    step++;
                }
            }
            isDelete[p]=1;
            step=0;
        }
        return p;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

方法二 模拟法 改进

使用arrayList,每次删除完,动态调整列表的大小
优:
不用遍历已经删除的元素
缺:每次删除,耗时 0(n^2),可以勉强通过模拟器

   // 法2 
    public int lastRemaining02(int n, int m) {
        ArrayList<Integer> list = new ArrayList<>();
        int p=-1;
        for (int i = 0; i <n ; i++) {
            list.add(i);
        }
        // 进行遍历删除
        while (n>1){
            p=(p+m-1)%n;
            list.remove(p);
            n--;
        }
        return list.get(0);
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

方法三 数学解法

    public int lastRemaining03(int n, int m) {
        int ans=0;
        for (int i = 2; i <=n ; i++) {  // 最后一轮数组长度是2
            ans=(ans+m)%i;
        }
        return ans;
    }
1
2
3
4
5
6
7