环形链表的约瑟夫问题

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

热度指数：25473 时间限制：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

输出

算法知识视频讲解

Javascript

JTY520

暴力破解法：直接循环遍历，重置数组

function ysf( n ,  m ) {
    // write code here
    let user = [];
    for(let i = 1; i <= n; i ++) {
        user.push(i)
    }
    while(user.length > 1) {
        let index = m % user.length;
        if (index == 0) {
            user.pop();
        } else {
            user = user.slice(index, user.length).concat(user.slice(0, index - 1));
        }
    }
    return user[0];
}

发表于 2022-01-17 00:28:18 回复(0)

Javascript

牛客553342978号

发表于 2021-12-18 17:04:56 回复(0)

JavaScript

splwany

function ysf( n ,  m ) {
    if (n < 1 || m < 1) return null;
    let last = 0;
    for (let i = 2; i <= n; i++) last = (last + m) % i;
    return last + 1;
}

发表于 2021-04-18 16:01:35 回复(0)