题目难度: 简单
今天继续更新剑指 offer 系列, 老样子晚上 6 点 45 分准时更新公众号 每日精选算法题, 大家记得关注哦~ 另外在公众号里回复 offer 就能看到剑指 offer 系列当前连载的所有文章了
题目描述
0,1,,n-1 这 n 个数字排成一个圆圈，从数字 0 开始，每次从这个圆圈里删除第 m 个数字。求出这个圆圈里剩下的最后一个数字。
例如，0、1、2、3、4 这 5 个数字组成一个圆圈，从数字 0 开始每次删除第 3 个数字，则删除的前 4 个数字依次是 2、0、4、1，因此最后剩下的数字是 3。
- 1 <= n <= 10^5
- 1 <= m <= 10^6
题目样例
示例
输入: n = 5, m = 3
输出: 3
输入: n = 10, m = 17
输出: 2
题目思考
- n 个数字和 n-1 个数字最后剩下的数字有什么关系吗?
解决方案
思路
- 一个比较容易想到的思路是暴力法, 即使用数组模拟整个过程: 记录当前起点, 求要移除的下个数字的下标, 并从原列表中移除它. 但这样时间复杂度达到了 O(N^2), 因为移除元素也需要 O(N) 时间
- 而改用双端链表的话则为 O(MN), 因为虽然移除变为了 O(1), 但每次定位下一个要移除的数字下标时不能像数组那样 O(1) 时间定位, 而是需要 O(M) 时间来遍历到下个移除的位置
- 那有什么方法可以做到更小的时间复杂度呢?
- 如果我们能从 n-1 个数字的结果, 推导出 n 个数字的结果, 那就可以一次遍历 O(N) 时间搞定
- 所以尝试动态规划的思路, 设
dp[n, m]是 n 个数字时每次删除第 m 个数字的最后剩下数字的下标 - 第一次删除时, 删除数字的下标 i 为
(m-1)%n, 而其下一个下标 i+1 为下一次删除的起点 - 此时将新的起点 i+1 映射为下标 0, 自然 i+2 就对应下标 1, ... 到最后原下标 i 就对应映射下标 n-2. 这样就转换成了 n-1 个数字时每次删除第 m 个数字的情况
- 显然映射下标 x 与原下标 y 的关系是
y = (x+i+1)%n, 而 i 为(m-1)%n, 所以可以进一步得到y = (x+m)%n - 下标映射之后, 此时总共有 n-1 个数字, 最终剩余的数字就是
dp[n-1,m], 这个是映射下标, 根据上面的下标转换关系, 反推出原下标就是(dp[n-1,m]+m)%n - 而不管是第一次删除还是第二次删除, 其最终剩余的数字只能是同一个, 所以
dp[n, m] = (dp[n-1,m]+m)%n, 这就是最核心的状态转移方程 - 观察可以发现, 每个 dp 值只和前一个 dp 值相关, 所以我们可以使用一个变量来节省空间, 然后从小到大遍历到 n 即可
- 而 dp 初始值为 n=1 的情况, 此时最后剩余的数字显然只能是 0
复杂度
- 时间复杂度 O(N): 只需要遍历到 N
- 空间复杂度 O(1): 只使用了常数个变量
代码
class Solution:
def lastRemaining(self, n: int, m: int) -> int:
# 初始dp[1,m]为0
dp = 0
for x in range(2, n + 1):
# 对应公式dp[x,m] = (dp[x-1,m] + m) % x
dp = (dp + m) % x
return dp 大家可以在下面这些地方找到我~😊
我的公众号: 每日精选算法题, 欢迎大家扫码关注~😊
京公网安备 11010502036488号