LeetCode:1184. 公交站间的距离 一次遍历数组，复杂度O(n)

1184. 公交站间的距离

today 1184 公交站间的距离

题目描述

环形公交路线上有 n 个站，按次序从 0 到 n - 1 进行编号。我们已知每一对相邻公交站之间的距离，distance[i] 表示编号为 i 的车站和编号为 (i + 1) % n 的车站之间的距离。

环线上的公交车都可以按顺时针和逆时针的方向行驶。

返回乘客从出发点 start 到目的地 destination 之间的最短距离。

示例 1：

输入：distance = [1,2,3,4], start = 0, destination = 1
输出：1
解释：公交站 0 和 1 之间的距离是 1

示例 2：

输入：distance = [1,2,3,4], start = 0, destination = 2
输出：3
解释：公交站 0 和 2 之间的距离是 3

示例 3：

输入：distance = [1,2,3,4], start = 0, destination = 3
输出：4
解释：公交站 0 和 3 之间的距离是 4

提示：

• 1 <= n <= 10^4
• distance.length == n
• 0 <= start, destination < n
• 0 <= distance[i] <= 10^4

题目解析

这道题目是一道关于环形公交路线的题目。

首先，我们可以将环形公交路线看作是一个环，然后我们可以从 start 出发，沿着顺时针方向行驶，直到到达 destination，这样得到的距离为sum1。
我们再从 destination 出发，沿着逆时针方向行驶，直到到达 start，这样得到的距离为sum2，最后我们返回 min(sum1, sum2)。
值得注意的是，sum1和sum2的和为整个环路的距离。因此我们可以通过一次遍历，解决问题。

复杂度分析：

• 时间复杂度：$O(n)$
• 空间复杂度：$O(1)$

代码实现

Python版本：

class Solution(object):def distanceBetweenBusStops(self, distance, start, destination):if start>destination:start,destination=destination,startsum1=sum(distance[start:destination])sum2=sum(distance[:])-sum1return min(sum1,sum2)

C++版本：

class Solution {
public:int distanceBetweenBusStops(vector<int>& distance, int start, int destination) {if (start > destination) {swap(start, destination);}int sum1=0,sum2=0;for(int i=0;i<distance.size();i++){if(i>=start&&i<destination)sum1+=distance[i];elsesum2+=distance[i];}return min(sum1,sum2);}
};

Go版本：

func distanceBetweenBusStops(distance []int, start, destination int) int {if start > destination {start, destination = destination, start}sum1, sum2 := 0, 0for i, j := range distance {if start <= i && i < destination {sum1 += j} else {sum2 += j}}return min(sum1, sum2)
}