What is the easiest way to simulate the circular track visits?

Use an array of size n and increment counts for each sector visited, applying modulo arithmetic to handle wrap-around.

Why does the problem require sorting the result array?

Sorting ensures the sectors are returned in ascending order, which is explicitly required in the problem statement.

Can this problem be solved without simulating each sector visit?

Yes, by using range counting between start and end sectors, but explicit simulation aligns with the array plus simulation pattern.

How do I handle rounds that wrap around from n to 1?

Use modulo arithmetic to loop back to sector 1 when the end sector index exceeds n, maintaining correct visit counts.

Which pattern does this problem emphasize for interview solutions?

This problem emphasizes the Array plus Simulation pattern, focusing on visit counting and circular traversal handling.

#1560

Easy

auto_awesome数组·模拟

LeetCode 题解工作台

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

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

数组模拟

题目描述

给你一个整数 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

lightbulb

解题思路

方法一：考虑开始、结束的位置关系

由于每个阶段的结束位置是下一个阶段的开始位置，并且每个阶段都是逆时针方向的，所以我们可以根据开始和结束的位置关系来确定每个扇区的经过次数。

如果 $\textit{rounds}[0] \leq \textit{rounds}[m]$ ，那么从 $\textit{rounds}[0]$ 开始，到 $\textit{rounds}[m]$ 结束的所有扇区经过的次数是最多的，我们可以直接返回这个区间内的所有扇区。

否则，从 $1$ 开始，到 $\textit{rounds}[m]$ 结束的所有扇区和从 $\textit{rounds}[0]$ 开始，到 $n$ 结束的所有扇区的并集是经过次数最多的，我们可以返回这两个区间的并集。

时间复杂度 $O(n)$ ，其中 $n$ 是扇区的个数。忽略答案数组的空间消耗，空间复杂度 $O(1)$ 。

1

2

3

4

5

6

class Solution:
    def mostVisited(self, n: int, rounds: List[int]) -> List[int]:
        if rounds[0] <= rounds[-1]:
            return list(range(rounds[0], rounds[-1] + 1))
        return list(range(1, rounds[-1] + 1)) + list(range(rounds[0], n + 1))

speed

复杂度分析

指标	值
时间	complexity is O(n + m) where n is the number of sectors and m is the number of rounds, as each round is simulated efficiently. Space complexity is O(n) for the array storing visit counts of each sector.
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
Ask about simulating rounds efficiently without revisiting sectors unnecessarily.
question_mark
Check if the candidate handles circular wrap-around correctly using modulo arithmetic.
question_mark
Listen for reasoning about using an array to count visits versus more complex data structures.

warning

常见陷阱

外企场景

error
Failing to account for circular wrap-around, causing incorrect visit counts.
error
Using nested loops unnecessarily, which increases time complexity.
error
Forgetting to sort the result array, leading to incorrect output order.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Return the least visited sectors instead of the most visited sectors.
arrow_right_alt
Simulate a track with variable-length rounds or weighted visits.
arrow_right_alt
Handle a dynamic number of sectors added or removed between rounds.

help

常见问题

外企场景

继续练习