做基本的网站,中国建设教育协会网站培训中心,网站建设需要用到什么,三五做网站文章目录 Tag题目来源解题思路方法一#xff1a;差分 写在最后 Tag
【差分数组】【数组】【2023-12-02】 题目来源
1094. 拼车 解题思路
本题朴素的解题思路是统计题目中提到的每一个站点的车上人数#xff0c;如果某个站点的车上人数大于车上的座位数直接返回 false… 文章目录 Tag题目来源解题思路方法一差分 写在最后 Tag
【差分数组】【数组】【2023-12-02】 题目来源
1094. 拼车 解题思路
本题朴素的解题思路是统计题目中提到的每一个站点的车上人数如果某个站点的车上人数大于车上的座位数直接返回 false如果直到行程结束都没有返回 false则直接返回 true。朴素方法的时间复杂度为 O ( n 2 ) O(n^2) O(n2) n n n 最大为 1000该方法时间复杂度较高但是可以通过本题。
接下来将会介绍一种时间复杂度较优的方法时间复杂度为 O ( n U ) O(n U) O(nU)。
方法一差分
我们先来看一下朴素方法的实现代码
class Solution {
public:bool carPooling(vectorvectorint trips, int capacity) {vectorint peoples(10010);for (auto trip : trips) {for (int i trip[1]; i trip[2]; i) {peoples[i] trip[0];if (peoples[i] capacity) {return false;}}}return true;}
};注意观察朴素解法中对于数组 peoples 的更新我们枚举并更新所有站点的车上人数朴素方法的时间复杂度较高的原因就是此处的嵌套枚举更新人数。此处可以使用【差分数组】来优化时间复杂度。
什么是差分数组
差分数组是一个与原数组长度相同的数组其中除了首元素其余的每个元素都是原数组中相邻两个元素的差值。比如数组 arr [1, 4, 5, 6] 的差分数组 diff [1, 3, 1, 1]数组 arr[i] diff[0, ..., i]即原数组 arr 中的第 i 个元素等于差分数组 diff 第 0 到第 i 个元素之和。
时间是如何优化的
对于某一段旅行有 numPassengers 乘客乘客上车点为 from下车点为 to这一段旅程的我们只需要更新差分数数组的两个位置对应的值即更新乘客上车点 diff[from] numPaaengers, 更新乘客下车点 diff[to] - numPaaengers。此时的时间复杂度为 O ( 2 × n ) O ( n ) O(2 \times n) O(n) O(2×n)O(n) n n n 为数组 trips 的长度。
然后利用差分数组累加得到每个站点的车上人数并与 capacity 比较… 此处的时间复杂度为 O ( U ) O(U) O(U) U m a x ( t o i ) U max(to_i) Umax(toi)。
我们借助差分数组将嵌套枚举转化为了两个线性枚举大大降低了时间复杂度。
实现代码
class Solution {
public:bool carPooling(vectorvectorint trips, int capacity) {int d[1001];memset(d, 0, sizeof(d));for (auto trip : trips) {int num trip[0], from trip[1], to trip[2];d[from] num;d[to] - num;}int s 0;for (int v : d) {s v;if (s capacity) {return false;}}return true;}
};复杂度分析
时间复杂度 O ( n U ) O(n U) O(nU) n n n 为数组 trips 的长度 U m a x ( t o i ) U max(to_i) Umax(toi)。
空间复杂度 O ( U ) O(U) O(U)。 写在最后
如果文章内容有任何错误或者您对文章有任何疑问欢迎私信博主或者在评论区指出 。
如果大家有更优的时间、空间复杂度方法欢迎评论区交流。
最后感谢您的阅读如果感到有所收获的话可以给博主点一个 哦。
