题目描述

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

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

限制：

• 1 <= n <= 10^5
• 1 <= m <= 10^6

测试用例

示例 1：

• 输入: n = 5, m = 3
• 输出: 3

示例 2：

输入: n = 10, m = 17 输出: 2

思路

参考了这篇文章 (opens new window)的解法，分析的非常到位

代码实现

var __readline = require("readline-sync");
__readline.setDefaultOptions({ prompt: "" });
var readline = __readline.prompt;

console.log("请输入数字个数n: ");
const n = parseInt(readline());

console.log("请输入你每次要删除第几个数字m: ");
const m = parseInt(readline());

/**
 * @param {number} n
 * @param {number} m
 * @return {number}
 */
var lastRemaining = function (n, m) {
  // 约瑟夫环
  // 从后往前推
  // 最后剩的数字下标一定是0 —— 现在数字长度为1
  let survivorIndex = 0;

  // 数字长度1反推长度2 —— 长度2反推长度3 ....
  for (let numsLen = 2; numsLen <= n; numsLen++) {
    survivorIndex = (survivorIndex + m) % numsLen;
  }
  return survivorIndex;
};

const res = lastRemaining(n, m);
console.log("结果为: ", res);

/* 
  请输入数字个数n:
  5
  请输入你每次要删除第几个数字m:
  3
  结果为:  3

  请输入数字个数n:
  10
  请输入你每次要删除第几个数字m:
  17
  结果为:  2
*/