题目描述:0,1,,n-1 这 n 个数字排成一个圆圈,从数字 0 开始,每次从这个圆圈里删除第 m 个数字。求出这个圆圈里剩下的最后一个数字。例如,0、1、2、3、4 这 5 个数字组成一个圆圈,从数字 0 开始每次删除第 3 个数字,则删除的前 4 个数字依次是 2、0、4、1,因此最后剩下的数字是 3。
示例:
输入: n = 5, m = 3
输出: 3
可以发现:
可以将上面的规律写成循环,第 n 次的结果等于:(上次一次结果 + m)%n
代码实现如下:
// ac地址:https://leetcode-cn.com/problems/yuan-quan-zhong-zui-hou-sheng-xia-de-shu-zi-lcof/
// 原文地址:https://xxoo521.com/2020-04-19-last-remain-number/
/**
* @param {number} n
* @param {number} m
* @return {number}
*/
var lastRemaining = function(n, m) {
let result = 0;
for (let i = 2; i <= n; ++i) {
result = (result + m) % i;
}
return result;
};
时间复杂度是O(N),空间复杂度是O(1)。
尝试了下这种做法,会 TLE。因为时间复杂度是 O(m*n)。