面试题62. 圆圈中最后剩下的数字
in LeetCode with 0 comment

面试题62. 圆圈中最后剩下的数字

?> with 0 comment

题目

0,1,,n-1这n个数字排成一个圆圈,从数字0开始,每次从这个圆圈里删除第m个数字。求出这个圆圈里剩下的最后一个数字。

例如,0、1、2、3、4这5个数字组成一个圆圈,从数字0开始每次删除第3个数字,则删除的前4个数字依次是2、0、4、1,因此最后剩下的数字是3。

示例 1:

输入: n = 5, m = 3
输出: 3


示例 2:

输入: n = 10, m = 17
输出: 2


限制:

1 <= n <= 10^5
1 <= m <= 10^6

暴力解法

我的第一反应是,将每次的起点的记录下来,然后计算( x + m - 1 ) % len(data)

写出的代码如下:

class Solution:
    def lastRemaining(self, n: int, m: int) -> int:
        data = [i for i in range(n)]
        new_m = m - 1
        index = 0
        while(len(data) != 1):
            # 当前的位置
            index += m - 1
            index %= len(data) 

            data = data[:index] + data[index+1:]
        return data[0]

结果应该是正确的,但实际上不可用,因为循环次数过多,计算复杂。

递推解法

首先将过程进行罗列:

如果我们用

问题1:如果我们知道 5 个数的时候,最终 2 会留下来。那么 4 个数字的时候,谁会留下来呢?

回答1:当第一次把 2 删除之后,所有的元素都前进了 3 位(因为重新从3开始排序的原因)。 所以4个人的时候,第 0 个位置的会留到最后。

问题2: 如果我们知道 4 个数字的时候,第0个位置的会留下来。那么 5 个数字的时候,谁会留下来?

回答2: 这是上一个问题的逆过程,所有元素向后退 3 个元素即可。因此 f(5,3) = f(4,3) + 3 ,但数组存在越界问题,因此 f(5,3) = f(4,3) + 3 % 5

于是递推公式可以为:

当前位置要删除的元素,应该是 (上次的起点 + m ) %当前长度 得到,那么可以递推得到

class Solution:
    def lastRemaining(self, n: int, m: int) -> int:
        ans = 0
        # 最后 1 位为最终保留数字
        # 往前逆推,从元素个数为 2 开始
        for i in range(2, n + 1):
            # 逆推公式
            ans = (ans + m) % i
        
        return ans
Responses

From now on, bravely dream and run toward that dream.
陕ICP备17001447号·苏公网安备 32059002001895号