圆形赛道上经过次数最多的扇区

标签: 数组 模拟

难度: Easy

给你一个整数 n 和一个整数数组 rounds 。有一条圆形赛道由 n 个扇区组成，扇区编号从 1 到 n 。现将在这条赛道上举办一场马拉松比赛，该马拉松全程由 m 个阶段组成。其中，第 i 个阶段将会从扇区 rounds[i - 1] 开始，到扇区 rounds[i] 结束。举例来说，第 1 阶段从 rounds[0] 开始，到 rounds[1] 结束。

请你以数组形式返回经过次数最多的那几个扇区，按扇区编号 升序 排列。

注意，赛道按扇区编号升序逆时针形成一个圆（请参见第一个示例）。

示例 1：

输入：n = 4, rounds = [1,3,1,2]
输出：[1,2]
解释：本场马拉松比赛从扇区 1 开始。经过各个扇区的次序如下所示：
1 --> 2 --> 3（阶段 1 结束）--> 4 --> 1（阶段 2 结束）--> 2（阶段 3 结束，即本场马拉松结束）
其中，扇区 1 和 2 都经过了两次，它们是经过次数最多的两个扇区。扇区 3 和 4 都只经过了一次。

示例 2：

输入：n = 2, rounds = [2,1,2,1,2,1,2,1,2]
输出：[2]

示例 3：

输入：n = 7, rounds = [1,3,5,7]
输出：[1,2,3,4,5,6,7]

提示：

  • 2 <= n <= 100
  • 1 <= m <= 100
  • rounds.length == m + 1
  • 1 <= rounds[i] <= n
  • rounds[i] != rounds[i + 1] ，其中 0 <= i < m

Submission

运行时间: 24 ms

内存: 16.0 MB

class Solution:
    def mostVisited(self, n: int, rounds: List[int]) -> List[int]:
        start, end = rounds[0], rounds[-1]
        if start <= end:
            return list(range(start, end + 1))
        else:
            leftPart = range(1, end + 1)
            rightPart = range(start, n + 1)
            return list(itertools.chain(leftPart, rightPart))

Explain

该题解的核心思路是基于对圆形赛道的分析，即在一个圆形赛道上，选手从某一起点start到终点end跑步。如果起点start小于或等于终点end，那么选手是直接从start跑到end，这时候这之间所有的扇区都被跑过一次。如果起点start大于终点end，说明选手跑了一整圈又多跑了一段，这时候从1到end的扇区以及从start到n的扇区都被跑过。因此，题解直接根据起点和终点的相对位置，使用Python的range函数生成对应的扇区序列。

时间复杂度: O(n)

空间复杂度: O(n)

# 定义Solution类

class Solution:
    def mostVisited(self, n: int, rounds: List[int]) -> List[int]:
        start, end = rounds[0], rounds[-1]
        if start <= end:
            # 如果起点小于等于终点，直接返回这一段区间
            return list(range(start, end + 1))
        else:
            # 如果起点大于终点，说明跑过了整个赛道的一圈，需要分两部分返回
            leftPart = range(1, end + 1)  # 从1到end的部分
            rightPart = range(start, n + 1)  # 从start到n的部分
            # 使用itertools.chain连接两个部分的范围，并转化为列表返回
            return list(itertools.chain(leftPart, rightPart))

Explore

该解决方案没有准确地计算每个扇区被经过的次数，因为它只考虑了从起点到终点的路径。在多轮的情况下，中间的扇区可能被重复多次经过，特别是当完整的圆周被跑多次时。因此，解决方案需要进一步分析每个扇区在整个比赛中被经过的具体次数，尤其是考虑完整圆周的重复经过情况。

在Python中，`range(start, end)`函数生成的是一个从`start`到`end-1`的序列，即包含起点不包含终点的半开区间。因此，为了包含终点扇区，我们需要将终点`end`加一，使`range(start, end + 1)`实际上包含从`start`到`end`的所有扇区，确保终点扇区也被包括在内。

当前解决方案只考虑了起点和最终的终点，没有考虑到`rounds`数组中间的元素可能表示选手在比赛中重复经过某些扇区的情况。这意味着如果`rounds`数组中有重复经过某些扇区的情况，当前方法无法正确处理，因为它没有统计所有阶段中每个扇区被经过的次数。正确的方法应该是追踪和统计所有阶段中每个扇区的经过次数。