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

题目

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
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)

写出的代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
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]


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

递推解法

首先将过程进行罗列:

如果我们用

  • f(n,m) 表示 n 个数字,每次删除第 m 个元素,最终保留下来的元素编号

  • f(n-1,m) 表示 n 个数字时,每次删除第 m 个元素,最终留下来的元素编号。

问题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 ) %当前长度得到,那么可以递推得到

  • n = 1 时,要删除的元素:0;
  • n = 2 时,索引:(0 + m) % 2;
  • n = 3 时,索引:((0 + m) % 2 + m) % 3;
  • n = 4 时,索引:(((0 + m) % 2 + m) % 3 + m) % 4;
  • n = 5 时,索引:((((0 + m) % 2 + m) % 3 + m) % 4 + m) % 5。
1
2
3
4
5
6
7
8
9
10
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

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

https://iii.run/archives/8ca92480563c.html

作者

mmmwhy

发布于

2020-04-09

更新于

2021-05-30

许可协议