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

难度:

标签:

题目描述

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

代码结果

运行时间: 24 ms, 内存: 16.0 MB

/*
 思路：
 1. 使用IntStream来创建一个数组记录每个扇区经过的次数。
 2. 使用流操作更新每个阶段的开始和结束扇区。
 3. 使用取模运算来处理圆形赛道的循环。
 4. 找出经过次数最多的扇区，并按升序排序。
*/

import java.util.Arrays;
import java.util.List;
import java.util.stream.Collectors;
import java.util.stream.IntStream;

public class MarathonStream {
    public List<Integer> mostVisited(int n, int[] rounds) {
        int[] count = new int[n + 1];
        IntStream.range(1, rounds.length).forEach(i -> {
            int start = rounds[i - 1];
            int end = rounds[i];
            while (start != end) {
                count[start]++;
                start = start % n + 1;
            }
        });
        count[rounds[rounds.length - 1]]++;
        int maxCount = Arrays.stream(count).max().orElse(0);
        return IntStream.rangeClosed(1, n)
                .filter(i -> count[i] == maxCount)
                .boxed()
                .collect(Collectors.toList());
    }
}

解释

方法:

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

时间复杂度:

O(n)

空间复杂度:

O(n)

代码细节讲解

🦆

在解决方案中，如果选手完成了多个完整的圆周加上部分扇区，该算法是否准确地计算了每个扇区被经过的次数？

▷

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

🦆

该题解中使用了`range`函数来生成扇区序列，考虑到Python的range是半开区间，解释为何在`range(start, end + 1)`中需要对`end`加一来正确包含终点扇区？

▷

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

🦆

解决方案是通过分析起点与终点的相对位置来决定输出，这种方法是否适用于所有可能的`rounds`数组的输入？例如，如果`rounds`数组中间的元素表示重复经过某些扇区，当前方法是否能正确处理？

▷

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

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

题目描述

代码结果

解释

代码细节讲解

相关问题