每天一道leetcode(Day 2)

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

题目描述

0,1,,n-1 这 n 个数字排成一个圆圈，从数字 0 开始，每次从这个圆圈里删除第 m 个数字。求出这个圆圈里剩下的最后一个数字。

例如，0、1、2、3、4 这 5 个数字组成一个圆圈，从数字 0 开始每次删除第 3 个数字，则删除的前 4 个数字依次是 2、0、4、1，因此最后剩下的数字是 3。

示例

解题思路

方法一：暴力求解

使用数组进行模拟，将 n 个数字放入数组，假设当前所处的位置为 index,则下一次要删除的位置为 index + m,删除该位置元素后，整个数组的长度变为 n-1，可以使用取模的方法不断获取 index 的位置。直到数组中只剩 1 个元素即可。

代码：

/**
 * @param {number} n
 * @param {number} m
 * @return {number}
 */

var lastRemaining = function(n, m) {
  let arr = [];
  for (let i = 0; i < n; i++) {
    arr.push(i);
  }
  while (n > 1) {
    index = (index + m - 1) % n;
    arr.splice(index, 1);
    n--;
  }
  return arr[0];
};

方法二：迭代

当序列长度为 1 时，一定会留下唯一的那个元素，它的编号为 0，因此 lastRemaining(1, m)=0。由 lastRemaining(n, m) = (m + lastRemaining(n-1, m)) % n 可得迭代解法。

代码

var lastRemaining = function(n, m) {
  let res = 0;
  for (let i = 2; i <= n; i++) {
    res = (m + res) % i;
  }
  return res;
};

参考

• 62. 圆圈中最后剩下的数字