【LeetCode】面试题62. 圆圈中最后剩下的数字 解题报告(Python)

时间：2024-04-18 02:19:22

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

题目描述

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. 1 <= n <= 10^5
  2. 1 <= m <= 10^6

题目大意

n个数字排成了圆圈，每次删除第m个数字，看最后剩下哪个数字。

解题方法

约瑟夫环

这个题可以用约瑟夫环解决。你如果是第一次做这个题肯定不知道，方法就是总结出来的嘛，见多了就知道了。

理解约瑟夫环，我们采用倒推，我们倒推出：最后剩下的这个人，在最开始的数组中的位置。

  1. 剩下最后一个人（简称“他”）的时候，人数为1，他的位置pos = 0。
  2. 那么他在上一轮也是安全的，人数为2，他的位置pos = (0 + m) % 2；
  3. 那么他在上上轮也是安全的，人数为3，他的位置pos = ((0 + m) % 2 + m) % 3；
  4. 那么他在上上上轮也是安全的，人数为4，他的位置pos = (((0 + m) % 2 + m) % 3) % 4；
  5. …
  6. 那么他在游戏开始的第一轮也是安全的，人数为n，他的位置pos就是最后的结果。

即如果从下向上反推的时候：假如他前一轮的索引为pos，那么当前轮次的位置就是 (pos + m) % 当前轮次的人数。

最后，由于给出的数字是nums = 0,1,2..,n-1，即nums[i] = i，因此找出pos就相当于找到这个数字。

所以pos = 0开始，代表了最后结果只剩下了1个人，这个人处于第0个位置。

循环从数组长度有2个开始，即上一轮剩下了两个人。

循环到数组中剩下n个人结束，即到达了题目要求的那么多人，此时的pos就是最后剩下的那个人的在n个数字中位置。

Python代码如下：

class Solution:

    def lastRemaining(self, n: int, m: int) -> int:

        pos = 0

        for i in range(2, n + 1):

            pos = (pos + m) % i

        return pos

日期

2020 年 3 月 30 日 —— 近期在忙刷题交流群，没有时间写题解，抱歉