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

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

题目链接

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

题目描述

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

例如, 这  个数字组成一个圆圈,从数字  开始每次删除第  个数字,则删除的前  个数字依次是 ,因此最后剩下的数字是 。

示例1

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

示例2

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

说明:



题解

循环链表

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

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

递推法

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

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

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

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

用  表示  个人最后剩下的人编号,那么就有:

这样的话时间复杂度就降到了  。

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

递推法加速

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

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

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

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

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

数学法

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

具体数学-第8课(取整进阶)韦阳的博客:具体数学-第8课(取整进阶)[2]知乎专栏:具体数学-第8课(取整进阶)[3]知乎高赞回答也整理过了一遍:世界上有哪些代码量很少,但很牛逼很经典的算法或项目案例?[4]

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

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


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

其中  。

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

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

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

代码

递推法(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;
    }
};
相关文章
|
2月前
|
机器学习/深度学习 算法 数据挖掘
K-means聚类算法是机器学习中常用的一种聚类方法,通过将数据集划分为K个簇来简化数据结构
K-means聚类算法是机器学习中常用的一种聚类方法,通过将数据集划分为K个簇来简化数据结构。本文介绍了K-means算法的基本原理,包括初始化、数据点分配与簇中心更新等步骤,以及如何在Python中实现该算法,最后讨论了其优缺点及应用场景。
124 4
|
3月前
|
存储 算法 Java
解析HashSet的工作原理,揭示Set如何利用哈希算法和equals()方法确保元素唯一性,并通过示例代码展示了其“无重复”特性的具体应用
在Java中,Set接口以其独特的“无重复”特性脱颖而出。本文通过解析HashSet的工作原理,揭示Set如何利用哈希算法和equals()方法确保元素唯一性,并通过示例代码展示了其“无重复”特性的具体应用。
64 3
|
2天前
|
机器学习/深度学习 人工智能 算法
机器学习算法的优化与改进:提升模型性能的策略与方法
机器学习算法的优化与改进:提升模型性能的策略与方法
32 13
机器学习算法的优化与改进:提升模型性能的策略与方法
|
10天前
|
缓存 安全 Java
【JavaEE】——单例模式引起的多线程安全问题:“饿汉/懒汉”模式,及解决思路和方法(面试高频)
单例模式下,“饿汉模式”,“懒汉模式”,单例模式下引起的线程安全问题,解锁思路和解决方法
|
2月前
|
存储 算法 安全
SnowflakeIdGenerator-雪花算法id生成方法
SnowflakeIdGenerator-雪花算法id生成方法
27 1
|
2月前
|
存储 Java 程序员
Java基础的灵魂——Object类方法详解(社招面试不踩坑)
本文介绍了Java中`Object`类的几个重要方法,包括`toString`、`equals`、`hashCode`、`finalize`、`clone`、`getClass`、`notify`和`wait`。这些方法是面试中的常考点,掌握它们有助于理解Java对象的行为和实现多线程编程。作者通过具体示例和应用场景,详细解析了每个方法的作用和重写技巧,帮助读者更好地应对面试和技术开发。
137 4
|
3月前
|
算法 Java 数据库
美团面试:百亿级分片,如何设计基因算法?
40岁老架构师尼恩分享分库分表的基因算法设计,涵盖分片键选择、水平拆分策略及基因法优化查询效率等内容,助力面试者应对大厂技术面试,提高架构设计能力。
美团面试:百亿级分片,如何设计基因算法?
|
3月前
|
算法 前端开发 Java
数据结构与算法学习四:单链表面试题,新浪、腾讯【有难度】、百度面试题
这篇文章总结了单链表的常见面试题,并提供了详细的问题分析、思路分析以及Java代码实现,包括求单链表中有效节点的个数、查找单链表中的倒数第k个节点、单链表的反转以及从尾到头打印单链表等题目。
38 1
数据结构与算法学习四:单链表面试题,新浪、腾讯【有难度】、百度面试题
|
2月前
|
JSON 算法 数据挖掘
基于图论算法有向图PageRank与无向图Louvain算法构建指令的方式方法 用于支撑qwen agent中的统计相关组件
利用图序列进行数据解读,主要包括节点序列分析、边序列分析以及结合节点和边序列的综合分析。节点序列分析涉及节点度分析(如入度、出度、度中心性)、节点属性分析(如品牌、价格等属性的分布与聚类)、节点标签分析(如不同标签的分布及标签间的关联)。边序列分析则关注边的权重分析(如关联强度)、边的类型分析(如管理、协作等关系)及路径分析(如最短路径计算)。结合节点和边序列的分析,如子图挖掘和图的动态分析,可以帮助深入理解图的结构和功能。例如,通过子图挖掘可以发现具有特定结构的子图,而图的动态分析则能揭示图随时间的变化趋势。这些分析方法结合使用,能够从多个角度全面解读图谱数据,为决策提供有力支持。
110 0
|
3月前
|
机器学习/深度学习 算法 Java
机器学习、基础算法、python常见面试题必知必答系列大全:(面试问题持续更新)
机器学习、基础算法、python常见面试题必知必答系列大全:(面试问题持续更新)

热门文章

最新文章