【每日算法Day 74】经典面试题:约瑟夫环,我敢打赌你一定不会最后一种方法!...

题目链接

LeetCode 面试题62. 圆圈中最后剩下的数字

题目描述

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

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

示例1

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

      

示例2

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

      

说明:

题解

循环链表

用一个循环链表按顺序存储 0n-1 中的数,然后每 m 个数删除掉链表中的一个结点,最后剩下的数就是答案了。

这种方法时间复杂度是 O(nm) ,显然太高了,所以这里也不会给大家实现代码。

递推法

首先 n 个人的编号依次是 ,然后踢掉了编号为 的人,这时候剩下的人编号为

下一个踢掉的人就要从 开始数了,所以我们把剩下的人编号从 开始重新排个序,变成 。这样编号又变成连续的了,而问题规模缩减成了 n-1 个人。

剩下的这 n-1 个人的编号我们做一下映射,映射成 ,这样就能递推下去求解了。映射的公式就是,映射后的编号为 x ,那么映射之前的编号就是

也就是说,如果我们求出了 n-1 个人最后剩下的人编号 x ,那么 n 个人最后剩下的人编号就是

f(n) 表示 n 个人最后剩下的人编号,那么就有:

这样的话时间复杂度就降到了 O(n)

对于本题这个方法已经够用了,但是如果 n 非常大,比如 ,但是 m 不是很大,比如 ,那么这时候这种方法就会超时了。具体的题目请自行百度 HDU 3089 。

递推法加速

注意观察上面的递推式 ,如果 m 很小,而 n 很大的话,递推到后面要加很多次 m 才会对 n 求余。所以我们可以直接一下子加很多次 m ,然后再求余,这样就能加速了。

加了 tm 之后,递推式变成了:

假设加了 tm 之后才产生了取余,那么就有 ,即 。所以每次都可以加 m ,代码实现时用下取整,也就是

此外还需要注意,如果发现 ,也就是后面都不需要取余了,那么就直接一步加到底,退出循环得到答案。

这个方法时间复杂度不是很好分析,但应该也是对数级别的。

数学法

这个方法在我之前的文章中已经讲过了:

具体数学-第8课(取整进阶) | 韦阳的博客 godweiyang:具体数学-第8课(取整进阶)

知乎高赞回答也整理过了一遍:

世界上有哪些代码量很少,但很牛逼很经典的算法或项目案例?

大致思想也是重新编号,做编号映射,但是和上面递推法不同的是复杂度降到了对数级别。

这里就不详细讲了,大家可以去看上面的文章,这里直接给出伪代码:

        D = 1
while D <= (m-1)n:
    D = k
ans = mn+1-D
      

其中

不过这个这里的编号是 1n ,所以最后答案要减去 1

这种方法将时间复杂度降到了 ,用对数换底公式后得到

可以看出,这种方法适用于 n 特别大,但是 m 特别小的情况。否则的话如果 m 很大,分母会非常小,导致复杂度非常高。

代码

递推法(c++)

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

      

递推法加速(c++)

        class Solution {
public:
    int lastRemaining(int n, int m) {
        if (m == 1) return n-1;
        int last = 0, t = 1;
        for (int i = 2; i <= n; i+=t) {
            t = (i-last+m-3) / (m-1);
            if (i+t-1 > n) {
                last += (n-i+1)*m;
                break;
            }
            (last += t*m) %= (i+t-1);
        }
        return last;
    }
};

      

数学法(c++)

        class Solution {
public:
    int lastRemaining(int n, int m) {
        long D = 1, end = (long)n*(m-1);
        while (D <= end) {
            D = (m*D+m-2) / (m-1);
        }
        return (long)n*m-D;
    }
};

      

参考资料

[1]

LeetCode 面试题62. 圆圈中最后剩下的数字: leetcode-cn.com/problem

[2]

韦阳的博客:具体数学-第8课(取整进阶): godweiyang.com/2018/04/

[3]

知乎专栏:具体数学-第8课(取整进阶): zhuanlan.zhihu.com/p/35

[4]

世界上有哪些代码量很少,但很牛逼很经典的算法或项目案例?: zhihu.com/question/3582

算法码上来 文章被收录于专栏

公众号「算法码上来」。godweiyang带你学习算法,不管是编程算法,还是深度学习、自然语言处理算法都一网打尽,更有各种计算机新鲜知识和你分享。别急,算法码上来。

全部评论

相关推荐

10-05 23:02
东北大学 Java
我说句实话啊:那时候看三个月培训班视频,随便做个项目背点八股,都能说3 40w是侮辱价
点赞 评论 收藏
分享
今天 11:23
重庆邮电大学 C++
点赞 评论 收藏
分享
点赞 收藏 评论
分享
牛客网
牛客企业服务