圈圈中最后剩下的数字|博客系列
# 题目描述
0,1,...,n-1这n个数字排成一个圆圈，从数字0开始，每次从这个圆圈里删除第m个数字。求出这个圆圈里剩下的最后一个数字。
# 解题思路
解法一:链表解法
- 先创建一个
n长度的环形链表; - 记录下节点头的前一个节点
current,以保证我们找到需要删除的节点是current.next; - 每次循环
m找到目标节点进行删除,终止条件为节点的next为它自己; - 时间复杂度为
O(m*n),空间复杂度为O(n).
解法二:用数组模拟
每次计算下标，需要考虑末尾条件
# coding
解法一
/*
* 圈圈中最后一个数字
* @params{Number} m
* @params{Numner} n
* @returns{Number}
*/
function LastRemaining_Solution(n, m) {
if (n < 1 || m < 1) return -1
let loop = createListNodeLoop(n)
while (loop != loop.next) {
for (let i = 0; i < m - 1; i++) {
loop = loop.next
}
loop.next = loop.next.next
}
return loop.val
}
function createListNodeLoop(n) {
let head = {
val: 0
}
let current = head
for (let i = 1; i < n; i++) {
current.next = {
val: i
}
current = current.next
}
current.next = head
return current
}
@前端进阶之旅: 代码已经复制到剪贴板
解法二
/*
* 圈圈中最后一个数字
* @params{Number} m
* @params{Numner} n
* @returns{Number}
*/
function LastRemaining_Solution(n, m) {
if (n < 1 || m < 1) return -1
let array = Array.from({
length: n
}, (item, index) => index)
let index = 0;
while (array.length > 1) {
index = (index + m) % array.length - 1
if (index >= 0) {
array.splice(index, 1)
} else {
array.splice(array.length - 1, 1)
index = 0
}
}
return array[0]
}
@前端进阶之旅: 代码已经复制到剪贴板
测试代码
LastRemaining_Solution(10, 2)
// 4
@前端进阶之旅: 代码已经复制到剪贴板
