LeetCode 62 Joseph Circle

题目

LeetCode 62

给定一个长度为 n 的序列, 每次删除第 m 个元素，求最终留下的元素.

分析

开始看这道题, 是约瑟夫环问题, 就... 想链表. 但是, 时间复杂度太高.
但是想了许久, 发现好像可以通过子问题求解.

假设我们知道对于长度为 n - 1 的序列, 操作后留下的是元素, 那么我们就可以逆推出长度为 n 的序列的答案. 这里, 变好从 0 开始.

设 f(n, m) 表示长度为 n, 每次删除第 m 个元素, 最终留下的元素的序号.

那么, 第一次, 长度为 n 的序列会先删除第 m 个元素, 其实应该是 第 m % n 个元素，因为考虑到长度 n 小于 m 的情况. 然后长度变为 n - 1. 于是, 可以转化为一个递归的问题.

假设已求得 f(n - 1, m), 那么如何得到 f(n, m) 呢?

这里, ... 使用 LeetCode 上的一个图, 感觉很清晰.

所以, 我们设 f(n - 1, m) = x, 那么从图中不难看出,
f(n, m) = (m % n + x) % n.

结合递归边界, f(1, m) 一定是编号为度为 1 时，一定会留下编号为 0 的那个元素.

代码

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

其实, 也可以用循环来代替递归.

class Solution
{
public:
    int lastRemaining(int n, int m)
    {
        int rv = 0;

        for (int i = 2; i <= n; i++)
            rv = (rv + m) % i;

        return rv;
    }
};