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

谁借莪１个温暖的怀抱￠ 2023-09-27 12:17 119阅读 0赞

> **难度等级：简单**

> **上一篇算法：**
> 
> [剑指 Offer 64. 求1+2+…+n【数学】][Offer 64. _1_2_n]

> **力扣此题地址：**
> 
> [剑指 Offer 62. 圆圈中最后剩下的数字 - 力扣（LeetCode）][Offer 62. _ - _LeetCode]

### 1.题目： 圆圈中最后剩下的数字 ###

0,1,···,n-1这n个数字排成一个圆圈，从数字0开始，每次从这个圆圈里删除第m个数字（删除后从下一个数字开始计数）。求出这个圆圈里剩下的最后一个数字。

例如，0、1、2、3、4这5个数字组成一个圆圈，从数字0开始每次删除第3个数字，则删除的前4个数字依次是2、0、4、1，因此最后剩下的数字是3。

![866a39bd9e719060fb91440bc01fdd5a.png][]

### 2.解题思路： ###

> 递推公式：
> 
>   f\[1\]=0;
> 
>   f\[i\]=(f\[i-1\]+m)%i; (i>1)

### 3.代码实现： ###

class Solution {
        /*
        思路：使用数学方法(先举例)
                你要知道最后的结果是3，带着结果去看问题
    
            第一次，【0, 1, 2, 3, 4】，本轮要踢出2                                  看3
            (下一轮开始从3计数，为了方便读者看出规律，将开始计数的那一位移到开头)
            第二次，【3, 4, 0, 1】，本轮要踢出0                                     看1
            第三次，【1, 3, 4】，本轮要踢出4                                        看1
            第四次，【1, 3】 本轮要踢出1                                            看3
            第五次，【3】
            最后返回3
    
            我们要使用的数学方法，就是从结果0号位置，反推最开始在哪
            你从第二次，向上看第一次
            你会发现，原来3在0的位置
                    现在，3在(0 + 3) % 5
                            => +3 回到上次的位置
                            => %5 防止数组溢出，并且数组本来就是循环数组
    
            f(n) = ( f(n - 1) + m ) % n
            解释意思：
                f(n) 表示上一次
                f(n - 1) 表示这次，因为我们要从这次回推上一次
                m 表示隔几个
                n表示上一次的数组长度
    
         */
        public int lastRemaining(int n, int m) {
    
            if(n<1 || m<1)
                return -1;
    
            int last = 0;// 最后只剩下一位，坐标肯定是0
    
            for (int i = 2; i <= n; i++) {
                last = (last + m) % i;
            }
    
            return last;
        }
    }

[Offer 64. _1_2_n]: https://blog.csdn.net/m0_51697147/article/details/127489882
[Offer 62. _ - _LeetCode]: https://leetcode.cn/problems/yuan-quan-zhong-zui-hou-sheng-xia-de-shu-zi-lcof/
[866a39bd9e719060fb91440bc01fdd5a.png]: https://img-blog.csdnimg.cn/img_convert/866a39bd9e719060fb91440bc01fdd5a.png