Question

面试题 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

解法

方法一：数学 + 递归（迭代）

我们不妨设 $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)$。

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:
  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
}