剑指 Offer !!62. 圆圈中最后剩下的数字(约瑟夫环问题)

剑指 Offer 62. 圆圈中最后剩下的数字
简单
818
相关企业
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

一个很通俗易懂的题解
这个题解的缺点在于,推导过程有些粗糙……从一个案例直接退出递推公式。
优点在于,通俗易懂。
左程云的书(《程序员代码面试指南》第2版)上有一个还算规范的推导。

// 解法一:模拟法
   public int lastRemaining1(int n, int m) {
        ArrayList<Integer> list = new ArrayList();
        for(int i=0;i<n;i++){
            list.add(i);
        }
        int idx=0;

        while(n>1){
            idx = (idx+m-1)%n;// the one ready to be killed
            list.remove(idx);
            n--;
        }
        // now,n=1 means only one person is left
        return list.get(0);
    }

// 解法二:从最后一轮(幸存者的下标ans为0)开始,向前推,每次推上一轮这个幸存者的下标是什么,直到圈子长度为n为止,返回此时幸存者的下标
    public int lastRemaining(int n, int m) {
        int ans=0;
        for(int i=2;i<=n;i++){
        // 上一轮圈子的长度为i
            ans = (ans+m)%i;
         // 此时,ans为 在上一轮圈子中幸存者的下标
        }
        return ans;
    }

本图文内容来源于网友网络收集整理提供,作为学习参考使用,版权属于原作者。
THE END
分享
二维码
< <上一篇
下一篇>>