环形链表的约瑟夫问题

[编程题]环形链表的约瑟夫问题

热度指数：24799 时间限制：C/C++ 2秒，其他语言4秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

编号为 1 到 n 的 n 个人围成一圈。从编号为 1 的人开始报数，报到 m 的人离开。

下一个人继续从 1 开始报数。

n-1 轮结束以后，只剩下一个人，问最后留下的这个人编号是多少？

数据范围： $1 \le n , m \le 10000$

进阶：空间复杂度 $O(1)$ ，时间复杂度 $O(n)$

示例1

输入

5,2

输出

说明

开始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

输出

算法知识视频讲解

执子一白

发表于 2020-12-01 19:30:03

根据题意，正常构造链表满足条件删除即可别投机取巧，自己手打一遍熟悉熟悉 import java.util.*; public class Solution { /** * * @param n int整型 * @param m int整型 * 展开全文

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 展开全文

悟空WK

发表于 2020-11-27 09:28:35

牛客题霸NC132环形链表的约瑟夫问题Java题解https://www.nowcoder.com/practice/41c399fdb6004b31a6cbb047c641ed8a?tpId=117&&tqId=35273&rp=1&ru=/ta/job-code- 展开全文

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 √, 展开全文

棒棒糖🍭201906101800876

发表于 2021-10-12 11:37:29

NC132 环形链表的约瑟夫问题题目描述编号为 1 到 n 的 n 个人围成一圈。从编号为 1 的人开始报数，报到 m 的人离开。下一个人继续从 1 开始报数。 n-1 轮结束以后，只剩下一个人，问最后留下的这个人编号是多少？ 1. 暴力解法没什么好说的，用一个数组模拟整个过程，n-1轮循环展开全文

bigsai

发表于 2022-02-12 15:56:35

循环链表模拟这个问题最本质其实就是循环链表的问题，围成一个圈之后，就没有结尾这就是一个典型的循环链表嘛！一个一个顺序报数，那不就是链表的遍历枚举嘛！数到对应数字的出列，这不就是循环链表的删除嘛！并且这里还有非常方便的地方：循环链表的向下枚举不需要考虑头尾问题，直接node=node.nex 展开全文

viod

发表于 2021-06-09 17:39:45

约瑟夫环问题(变态杀人狂、围圈报数、猴子选大王等)有四种解题方法：1、循环链表法 2、数组标记法 3、数组链接法。这三种是基于模拟实现的，时间复杂度为O(n*m)，当n和m取值很大时，效率低，比如m取100w时(数到100w才淘汰)，即使只剩下了最后两个人，也要循环100w次才能出结果。学计算机展开全文