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
  • 对于 0 <= i < m，rounds[i] != rounds[i + 1]

解题思路

这道题有两种思路：

思路一：模拟计数法 直接模拟马拉松过程，统计每个扇区的访问次数。遍历每一轮比赛，从起始扇区到结束扇区，对经过的每个扇区计数。需要注意环形赛道的特性，当扇区编号超过 n 时要回到 1。

思路二：数学规律法（推荐） 通过观察可以发现一个重要规律：除了起点和终点，中间所有轮次的路径都是完整的一圈，因此每个扇区的访问次数都相同。真正影响访问次数差异的只有从总起点到总终点的路径。

具体来说：

  • 如果起点 ≤ 终点，那么访问次数最多的就是从起点到终点的连续扇区
  • 如果起点 > 终点，那么访问次数最多的是从 1 到终点，再加上从起点到 n 的扇区

这种方法的时间复杂度更优，代码也更简洁。

代码实现

class Solution {
public:
    vector<int> mostVisited(int n, vector<int>& rounds) {
        int start = rounds[0];
        int end = rounds.back();
        vector<int> result;
        
        if (start <= end) {
            for (int i = start; i <= end; i++) {
                result.push_back(i);
            }
        } else {
            for (int i = 1; i <= end; i++) {
                result.push_back(i);
            }
            for (int i = start; i <= n; i++) {
                result.push_back(i);
            }
        }
        
        return result;
    }
};

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:
            return list(range(1, end + 1)) + list(range(start, n + 1))

public class Solution {
    public IList<int> MostVisited(int n, int[] rounds) {
        int start = rounds[0];
        int end = rounds[rounds.Length - 1];
        List<int> result = new List<int>();
        
        if (start <= end) {
            for (int i = start; i <= end; i++) {
                result.Add(i);
            }
        } else {
            for (int i = 1; i <= end; i++) {
                result.Add(i);
            }
            for (int i = start; i <= n; i++) {
                result.Add(i);
            }
        }
        
        return result;
    }
}

var mostVisited = function(n, rounds) {
    const start = rounds[0];
    const end = rounds[rounds.length - 1];
    const result = [];
    
    if (start <= end) {
        for (let i = start; i <= end; i++) {
            result.push(i);
        }
    } else {
        for (let i = 1; i <= end; i++) {
            result.push(i);
        }
        for (let i = start; i <= n; i++) {
            result.push(i);
        }
    }
    
    return result;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

解法时间复杂度空间复杂度
数学规律法O(n)O(1)
模拟计数法O(m × n)O(n)

其中 m 是轮数，n 是扇区数量。推荐使用数学规律法，效率更高。