您的位置:首页 > 娱乐 > 明星 > LeetCode:1184. 公交站间的距离 一次遍历数组,复杂度O(n)

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

2024/11/8 15:20:31 来源:https://blog.csdn.net/weixin_60214397/article/details/142300982  浏览:    关键词:LeetCode:1184. 公交站间的距离 一次遍历数组,复杂度O(n)

1184. 公交站间的距离

today 1184 公交站间的距离

题目描述

环形公交路线上有 n 个站,按次序从 0n - 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)
值得注意的是,sum1sum2的和为整个环路的距离。因此我们可以通过一次遍历,解决问题。

复杂度分析:

  • 时间复杂度: O ( n ) O(n) O(n)
  • 空间复杂度: O ( 1 ) O(1) 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)
}

版权声明:

本网仅为发布的内容提供存储空间,不对发表、转载的内容提供任何形式的保证。凡本网注明“来源:XXX网络”的作品,均转载自其它媒体,著作权归作者所有,商业转载请联系作者获得授权,非商业转载请注明出处。

我们尊重并感谢每一位作者,均已注明文章来源和作者。如因作品内容、版权或其它问题,请及时与我们联系,联系邮箱:809451989@qq.com,投稿邮箱:809451989@qq.com