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

题目描述

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

解法

方法一：数学 + 递归

思考

每次删第 \(m\) 个，模拟链表是线性额外空间。删完一个后，剩下 \(n-1\) 人的编号可映射回原编号：\(f(n,m)=(m+f(n-1,m))\bmod n\)，\(f(1,m)=0\)。递归求解。

我们不妨设 \(f(n, m)\) 表示从 \(n\) 个数中每次删除第 \(m\) 个，最后剩下的是第几个数字。

我们第一次删除了第 \(m\) 个数字，剩下 \(n-1\) 个数，那么 \(x=f(n - 1, m)\) 就表示从剩下的 \(n-1\) 个数中，每次删除第 \(m\) 个，最后剩下的是第几个数字。

我们求得 \(x\) 之后，便可以知道 \(f(n, m)\) 应该是从 \(m \% n\) 开始数的第 \(x\) 个元素，即 \(f(n, m) = (m \% n + x) \% n\)。

当 \(n\) 为 \(1\) 时，最后留下的数字序号一定为 \(0\)。

递归求解即可，也可以改成迭代。

时间复杂度 \(O(n)\)，递归的空间复杂度 \(O(n)\)，迭代的空间复杂度 \(O(1)\)。

Python3JavaC++GoJavaScriptC#Swift

class Solution:
    def lastRemaining(self, n: int, m: int) -> int:
        def f(n, m):
            if n == 1:
                return 0
            x = f(n - 1, m)
            return (m + x) % n

        return f(n, m)

class Solution {
    public int lastRemaining(int n, int m) {
        return f(n, m);
    }

    private 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) {
        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;
    }
};

func lastRemaining(n int, m int) int {
    var f func(n, m int) int
    f = func(n, m int) int {
        if n == 1 {
            return 0
        }
        x := f(n-1, m)
        return (m + x) % n
    }
    return f(n, m)
}

/**
 * @param {number} n
 * @param {number} m
 * @return {number}
 */
var lastRemaining = function (n, m) {
    let f = 0;
    for (let i = 2; i <= n; ++i) {
        f = (f + m) % i;
    }
    return f;
};

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

class Solution {
    func lastRemaining(_ n: Int, _ m: Int) -> Int {
        return f(n, m)
    }

    private func f(_ n: Int, _ m: Int) -> Int {
        if n == 1 {
            return 0
        }
        let x = f(n - 1, m)
        return (m + x) % n
    }
}

方法二：数学 + 迭代

思考

递归深度为 \(n\)。同一递推自底向上从 \(2\) 滚到 \(n\)，只要一个变量，空间降为常数。

同一递推式自底向上计算。

Python3JavaC++Go

class Solution:
    def lastRemaining(self, n: int, m: int) -> int:
        f = 0
        for i in range(2, n + 1):
            f = (f + m) % i
        return f

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

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

func lastRemaining(n int, m int) int {
    f := 0
    for i := 2; i <= n; i++ {
        f = (f + m) % i
    }
    return f
}

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

题目描述

解法

方法一：数学 + 递归

方法二：数学 + 迭代

评论