首页 > 试题广场 >

环形链表的约瑟夫问题

[编程题]环形链表的约瑟夫问题
  • 热度指数：23131 时间限制：C/C++ 2秒，其他语言4秒 空间限制：C/C++ 256M，其他语言512M
  • 算法知识视频讲解
编号为 1 到 n 的 n 个人围成一圈。从编号为 1 的人开始报数，报到 m 的人离开。
下一个人继续从 1 开始报数。
n-1 轮结束以后，只剩下一个人，问最后留下的这个人编号是多少？

数据范围： 
进阶：空间复杂度 ，时间复杂度
示例1

输入

5,2

输出

3

说明

开始5个人 1，2，3，4，5 ，从1开始报数，1->1，2->2编号为2的人离开
1，3，4，5，从3开始报数，3->1，4->2编号为4的人离开
1，3，5，从5开始报数，5->1，1->2编号为1的人离开
3，5，从3开始报数，3->1，5->2编号为5的人离开
最后留下人的编号是3
示例2

输入

1,1

输出

1
算法知识视频讲解
开通博客
头像 执子一白
发表于 2020-12-01 19:30:03
根据题意，正常构造链表满足条件删除即可别投机取巧，自己手打一遍熟悉熟悉 import java.util.*; public class Solution { /** * * @param n int整型 * @param m int整型 * 展开全文
去ta的博客 赞 (22) 回复(3) 收起
头像 LifelongCode
发表于 2020-12-25 11:39:42
参考--剑指offer：圆圈中最后剩下的数字https://leetcode-cn.com/problems/yuan-quan-zhong-zui-hou-sheng-xia-de-shu-zi-lcof/solution/si-chong-fang-fa-xiang-xi-jie-da-by-y 展开全文
去ta的博客 赞 (14) 回复(1) 收起
头像 悟空GGG
发表于 2020-11-27 09:28:35
牛客题霸NC132环形链表的约瑟夫问题Java题解https://www.nowcoder.com/practice/41c399fdb6004b31a6cbb047c641ed8a?tpId=117&&tqId=35273&rp=1&ru=/ta/job-code- 展开全文
去ta的博客 赞 (10) 回复(2) 收起
头像 LourisXu
发表于 2021-08-05 00:06:15
数学如下表所示，每轮去掉的数的后一个数重新设置为0开头，重新排序0,1,2,...，然后逆向找对应的idx n m = 2 f(n,m) 5 0,√,2,3,4 f(5,2)=(f4,2)+2)%5=2 4 3,x,0,√,2 f(4,2)=(f(3,2)+2)%4=0 3 √, 展开全文
去ta的博客 赞 (8) 回复(0) 收起
头像 棒棒糖🍭201906101800876
发表于 2021-10-12 11:37:29
NC132 环形链表的约瑟夫问题 题目描述 编号为 1 到 n 的 n 个人围成一圈。从编号为 1 的人开始报数，报到 m 的人离开。 下一个人继续从 1 开始报数。 n-1 轮结束以后，只剩下一个人，问最后留下的这个人编号是多少？ 1. 暴力解法 没什么好说的，用一个数组模拟整个过程，n-1轮循环 展开全文
去ta的博客 赞 (8) 回复(0) 收起
头像 bigsai
发表于 2022-02-12 15:56:35
循环链表模拟 这个问题最本质其实就是循环链表的问题，围成一个圈之后，就没有结尾这就是一个典型的循环链表嘛！一个一个顺序报数，那不就是链表的遍历枚举嘛！数到对应数字的出列，这不就是循环链表的删除嘛！ 并且这里还有非常方便的地方： 循环链表的向下枚举不需要考虑头尾问题，直接node=node.nex 展开全文
去ta的博客 赞 (5) 回复(0) 收起
头像 viod
发表于 2021-06-09 17:39:45
约瑟夫环问题(变态杀人狂、围圈报数、猴子选大王等)有四种解题方法：1、循环链表法 2、数组标记法 3、数组链接法 。这三种是基于模拟实现的，时间复杂度为O(n*m)，当n和m取值很大时，效率低，比如m取100w时(数到100w才淘汰)，即使只剩下了最后两个人，也要循环100w次才能出结果。 学计算机 展开全文
去ta的博客 赞 (5) 回复(0) 收起
头像 阿邱
发表于 2021-05-26 09:09:32
利用报数的性质确定本轮淘汰的人员的索引，将其删除后，进行下一轮报数，直到剩下最后一个人 import java.util.*; public class Solution { /** * * @param n int整型 * @param m int整型 展开全文
去ta的博客 赞 (3) 回复(0) 收起
头像 牛客516598323号
发表于 2020-09-15 11:04:46
不会真的有人用链表做吧，不会吧不会吧。环形取余数组，逐一删除。用例通过率: 100.00% 运行时间: 44ms 占用内存: 6528KB。 # # # @param n int整型 # @param m int整型 # @return int整型 # class Solution: def 展开全文
去ta的博客 赞 (3) 回复(9) 收起
头像 小小小明哥
发表于 2022-01-17 19:47:05
class Solution { public: /** * * @param n int整型 * @param m int整型 * @return int整型 */ struct ListNode{ int v 展开全文
去ta的博客 赞 (3) 回复(2) 收起

问题信息

链表 基础数学
难度：
74条回答 3709浏览

热门推荐

通过挑战的用户

查看代码

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号