剑指Offer-面试题62-圆圈中最后剩下的数字

2020-05-12

题目描述

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

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

示例1：

1 2	输入: n = 5, m = 3 输出: 3

示例2：

1 2	输入: n = 10, m = 17 输出: 2

限制：

1 <= n <= 10^5
1 <= m <= 10^6

思路

约瑟夫环问题，有数学解法。
复制一份数组，以体现出环。
剑指Offer-面试题62-圆圈中最后剩下的数字
每次删除的是第m个数字（红色部分）

第一轮是[0, 1, 2, 3, 4]，所以是[0, 1, 2, 3, 4]这个数组的多个复制。这一轮2删除了。
第二轮开始时，从3开始，所以是[3, 4, 0, 1]这个数组的多个复制。这一轮0删除了。
第三轮开始时，从1开始，所以是[1, 3, 4]这个数组的多个复制。这一轮4删除了。
第四轮开始时，还是从1开始，所以是[1, 3]这个数组的多个复制。这一轮1删除了。
最后剩下的数字是3。

绿色的线指的是新一轮的开头是怎么指定的，每次都是固定地向前移动m个位置。
最后剩下的3的下标是0。

第四轮反推，补上m个位置，然后模上当时的数组大小2，位置是(0 + 3) % 2 = 1。
第三轮反推，补上m个位置，然后模上当时的数组大小3，位置是(1 + 3) % 3 = 1。
第二轮反推，补上m个位置，然后模上当时的数组大小4，位置是(1 + 3) % 4 = 0。
第一轮反推，补上m个位置，然后模上当时的数组大小5，位置是(0 + 3) % 5 = 3。
所以最终剩下的数字的下标就是3。因为数组是从0开始的，所以最终的答案就是3。

红色线指的就是从最后往前反推时3的位置。
总结一下反推的过程，就是(当前index + m) % 上一轮剩余数字的个数。

代码

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

作者：sweetieeyi
链接：https://leetcode-cn.com/problems/yuan-quan-zhong-zui-hou-sheng-xia-de-shu-zi-lcof/solution/javajie-jue-yue-se-fu-huan-wen-ti-gao-su-ni-wei-sh/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/yuan-quan-zhong-zui-hou-sheng-xia-de-shu-zi-lcof
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。