环形链表的约瑟夫问题

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

热度指数：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

输出

算法知识视频讲解

Python3

今天也要学习

class Solution:
    def ysf(self , n: int, m: int) -> int:
        nums = list(range(1,n+1))
        pos = 0
        for _ in range(n-1):
            pos = (pos+m-1)%len(nums)
            del nums[pos]
        return nums[0]

发表于 2025-01-08 13:13:13 回复(0)

Python3

NightRunner

o(nm) solution:

通过链表来模拟整个排除过程，时间复杂度较高，后面的例子会超时

    def ysf(self, n: int, m: int) -> int:
        # create circle
        head = ListNode(1)
        p = head
        for i in range(2, n+1):
            p.next = ListNode(i)
            p = p.next
        p.next = head
        # simulate process
        prev, curr, i = p, head, 1
        while curr.next != curr:
            if i % m == 0:
                # delete curr
                prev.next = curr.next
                i = 1
                curr = curr.next
                continue
            i += 1
            prev = curr
            curr = curr.next
        return curr.val

o(n)solution:

    def ysf(self, n: int, m: int) -> int:
        # 定义f(n)：当总共为n个人时，最后留下人的编号
        # 可以发现编号为f(n)的人在排除一个人后，形成的n-1子问题，编号对应关系是：f(n)=[f(n-1)+m-1]%n+1
        # f(1)=1, f(2)=1
        res = 1
        for i in range(1, n+1):
            res = (res+m-1) % i + 1
        return res

发表于 2021-11-11 18:25:35 回复(0)