圈圈中最后剩下的数字.md

题目描述

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

解题思路

解法一:链表解法

1. 先创建一个n长度的环形链表;
2. 记录下节点头的前一个节点current,以保证我们找到需要删除的节点是current.next;
3. 每次循环m找到目标节点进行删除,终止条件为节点的next为它自己;
4. 时间复杂度为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