Leetcode 面试题62.圆圈中最后剩下的数字【C++】

本文最后更新于:2020年11月19日 上午

地址: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 <= n <= 10^5
  • 1 <= m <= 10^6

解题思路

这题最容易想到的思路肯定是模拟真实的逐个删除的场景了,也就是暴力解,但是我并没有上来就这么做,我觉得这题肯定就不是让这么做的,暴力解存在挺大的问题,很傻,要遍历 n 次,逻辑也不是很好写。

自己想却真就想不出来好办法,后来看了官方题解,确实比暴力解好很多吧,但是实在不是我能想出来的,甚至有一个步骤( f(n, m)f(n - 1, m) 之间的关系)我看了题解也花了不少时间菜弄明白。具体的思路还是看官方题解吧,挺难用文字描述清楚的,这个题更偏向于数学问题,用数学的方法解体就简单很多。

同时官方题解分别用递归和迭代做了这个题,其实都是一个思路,理论上说递归更符合人的思路,但是 n 越大就要递归越深使用大量的栈空间,所以迭代是更好的办法,并且只需要一个变量保存相关数据,空间复杂度O(1)。

代码

递归:

class Solution {
public:
    int lastRemaining(int n, int m) {
        return f(n, m);
    }
    
    int f(int n, int m) {
        if (n == 1)
            return 0;
        int x = f(n - 1, m);
        return (m + x) % n;
    }
};

迭代:

class Solution {
public:
    int lastRemaining(int n, int m) {
        int f = 0;
        for (int i = 2; i != n + 1; ++i)
            f = (m + f) % i;
        return f;
    }
};