mantch

Inverview-62：圆圈中最后剩下的数字

《剑指offer》第二版(Python3实现):

https://github.com/NLP-LOVE/CodingInterviews2-ByPython

Inverview-62：圆圈中最后剩下的数字

题目：0,1,,n-1 这 n 个数字排成一个圆圈，从数字 0 开始，每次从这个圆圈里删除第 m 个数字。求出这个圆圈里剩下的最后一个数字。例如，0、1、2、3、4 这 5 个数字组成一个圆圈，从数字 0 开始每次删除第 3 个数字，则删除的前 4 个数字依次是 2、0、4、1，因此最后剩下的数字是 3。

这就是一个约瑟夫环问题。

解题思路

解题的一种方法是可以用环形链表来模拟圆圈，然后循环就可以解决了。但会发现环形链表重复遍历了很多遍，总的时间复杂度是 O(mn)。

还有一种方法是查看数字之间的规律，如下所述:

  • 首先我们定义一个关于 n 和m的方程 F(n,m)，表示每次在 n 个数字 0 到 n-1 中删除第 m 个数字最后剩下的数字。在这 n 个数字中，第一个被删除的数字是 (m-1)%n。为了简单起见，我们把 (m-1)%n 记为 k。

  • 删除 k 之后剩下的 n-1 个数字，并且下一次删除从数字 k+1 开始计数循环删除第 m 个数字，直到只剩下一个数字为止。我们可以定义这样的式子，F(n,m)=F(n-1,m)

  • 找规律: 接下来我们把删除过后的数字与从 0 开始计数的 n-2 的序列进行一一映射。

    会发现一个映射规律公式，P(x)=(x-k-1)%n。它表示如果映射前的数字是x，那么映射后的数字是 (x-k-1)%n。同样的，逆映射就是 Q(x)=(x+k+1)%n。

  • 接下来就是带入 F(n-1,m)。

    F(n-1,m) = Q[F(n-1,m)] = [F(n-1,m)+k+1]%n。

    把 k=(m-1)%n 代入

    F(n,m)=F(n-1,m) = [F(n-1,m)+m]%n

  • 最终我们就可以得到如下式子:

    根据这个公式我们就可以进行编程实现了，递归和循环都可以。

以下代码可提交至LeetCode：

https://leetcode-cn.com/problems/yuan-quan-zhong-zui-hou-sheng-xia-de-shu-zi-lcof/

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution:

    def lastRemaining(self, n: int, m: int) -> int:
        if n == 1:
            return 0

        last = 0
        for i in range(2, n + 1):
            last = (last + m) % i

        return last

n = 5
m = 3
s = Solution()
print(s.lastRemaining(n, m))

结果如下:

1
3


 上一页

 评论