题目：

0,1,,n-1这n个数字排成一个圆圈，从数字0开始，每次从这个圆圈里删除第m个数字。求出这个圆圈里剩下的最后一个数字。
例如，0、1、2、3、4这5个数字组成一个圆圈，从数字0开始每次删除第3个数字，则删除的前4个数字依次是2、0、4、1，因此最后剩下的数字是3。
示例 1：
输入: n = 5, m = 3
输出: 3
示例 2：
输入: n = 10, m = 17
输出: 2
限制：
1 <= n <= 10^5
1 <= m <= 10^6

题目的理解：

对“删除第3个数字”的理解是，当前指向的位置是1，然后删除下一个的下一个。如果是“删除第1个数字”，那么就是删除当前位置的数字。
按题目的理解，使用单链表实现了n个Node，然后每次删除第m个数字。

class Solution:
    def lastRemaining(self, n: int, m: int) -> int:
        class ListNode:
            def __init__(self, x):
                self.val = x
                self.next = None

        head = ListNode(0)
        current = head

        for index in range(1, n):
            current.next = ListNode(index)
            current = current.next

        current.next = head

        current = head

        while current.next != current:
            if m == 1:
                current.val = current.next.val
                current.next = current.next.next
            else:
                for _ in range(m - 2):
                    current = current.next

                current.next = current.next.next
                current = current.next

        return current.val

显然这样的时间复杂度为O(n + m*(n-1)),计算超时了。

如果不用单链接，直接用数组保存，那么时间复杂度为O(m*(n-1)).

class Solution:
    def lastRemaining(self, n: int, m: int) -> int:
        nums = list(range(n))
        index = 0

        while len(nums) > 1:
            for i in range(m - 1):
                index += 1

                if index >= len(nums):
                    index = 0

            nums.pop(index)

            if index >= len(nums):
                index = 0

        return nums[0]

还是计算超时了。!_!

将m的循环修改成index直接加m。 复杂度直接减m*(n - 1).

python实现

class Solution:
    def lastRemaining(self, n: int, m: int) -> int:
        nums = list(range(n))
        index = 0

        while len(nums) > 1:
            remain = len(nums) if m % len(nums) == 0 else m % len(nums)
            index += remain - 1

            if index >= len(nums):
                index -= len(nums)

            nums.pop(index)

            if index >= len(nums):
                index = 0

        return nums[0]

时间复杂度变成O(n).

想看最优解法移步此处

提交

ok

又见100%，难得难得

// END 说好开通的地铁，又要到下个月，等不了了现在就去瞧瞧