【每日一题】拼车+【差分数组】

2023-12-02 20:04
文章标签 数组 每日 差分 拼车

本文主要是介绍【每日一题】拼车+【差分数组】,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

文章目录

  • 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(n+U)

方法一:差分

我们先来看一下,朴素方法的实现代码:

class Solution {
public:bool carPooling(vector<vector<int>>& trips, int capacity) {vector<int> 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 个元素等于差分数组 diff0 到第 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) U=max(toi)

我们借助差分数组将嵌套枚举转化为了两个线性枚举,大大降低了时间复杂度。

实现代码

class Solution {
public:bool carPooling(vector<vector<int>>& 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(n+U) n n n 为数组 trips 的长度, U = m a x ( t o i ) U = max(to_i) U=max(toi)

空间复杂度: O ( U ) O(U) O(U)


写在最后

如果文章内容有任何错误或者您对文章有任何疑问,欢迎私信博主或者在评论区指出 💬💬💬。

如果大家有更优的时间、空间复杂度方法,欢迎评论区交流。

最后,感谢您的阅读,如果感到有所收获的话可以给博主点一个 👍 哦。

这篇关于【每日一题】拼车+【差分数组】的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/446626

相关文章

C++原地删除有序数组重复项的N种方法

《C++原地删除有序数组重复项的N种方法》给定一个排序数组,你需要在原地删除重复出现的元素,使得每个元素只出现一次,返回移除后数组的新长度,不要使用额外的数组空间,你必须在原地修改输入数组并在使用O(... 目录一、问题二、问题分析三、算法实现四、问题变体:最多保留两次五、分析和代码实现5.1、问题分析5.

Java中数组转换为列表的两种实现方式(超简单)

《Java中数组转换为列表的两种实现方式(超简单)》本文介绍了在Java中将数组转换为列表的两种常见方法使用Arrays.asList和Java8的StreamAPI,Arrays.asList方法简... 目录1. 使用Java Collections框架(Arrays.asList)1.1 示例代码1.

C++一个数组赋值给另一个数组方式

《C++一个数组赋值给另一个数组方式》文章介绍了三种在C++中将一个数组赋值给另一个数组的方法:使用循环逐个元素赋值、使用标准库函数std::copy或std::memcpy以及使用标准库容器,每种方... 目录C++一个数组赋值给另一个数组循环遍历赋值使用标准库中的函数 std::copy 或 std::

C++初始化数组的几种常见方法(简单易懂)

《C++初始化数组的几种常见方法(简单易懂)》本文介绍了C++中数组的初始化方法,包括一维数组和二维数组的初始化,以及用new动态初始化数组,在C++11及以上版本中,还提供了使用std::array... 目录1、初始化一维数组1.1、使用列表初始化(推荐方式)1.2、初始化部分列表1.3、使用std::

C++ Primer 多维数组的使用

《C++Primer多维数组的使用》本文主要介绍了多维数组在C++语言中的定义、初始化、下标引用以及使用范围for语句处理多维数组的方法,具有一定的参考价值,感兴趣的可以了解一下... 目录多维数组多维数组的初始化多维数组的下标引用使用范围for语句处理多维数组指针和多维数组多维数组严格来说,C++语言没

Java 字符数组转字符串的常用方法

《Java字符数组转字符串的常用方法》文章总结了在Java中将字符数组转换为字符串的几种常用方法,包括使用String构造函数、String.valueOf()方法、StringBuilder以及A... 目录1. 使用String构造函数1.1 基本转换方法1.2 注意事项2. 使用String.valu

JAVA中整型数组、字符串数组、整型数和字符串 的创建与转换的方法

《JAVA中整型数组、字符串数组、整型数和字符串的创建与转换的方法》本文介绍了Java中字符串、字符数组和整型数组的创建方法,以及它们之间的转换方法,还详细讲解了字符串中的一些常用方法,如index... 目录一、字符串、字符数组和整型数组的创建1、字符串的创建方法1.1 通过引用字符数组来创建字符串1.2

vue如何监听对象或者数组某个属性的变化详解

《vue如何监听对象或者数组某个属性的变化详解》这篇文章主要给大家介绍了关于vue如何监听对象或者数组某个属性的变化,在Vue.js中可以通过watch监听属性变化并动态修改其他属性的值,watch通... 目录前言用watch监听深度监听使用计算属性watch和计算属性的区别在vue 3中使用watchE

hdu2241(二分+合并数组)

题意:判断是否存在a+b+c = x,a,b,c分别属于集合A,B,C 如果用暴力会超时,所以这里用到了数组合并,将b,c数组合并成d,d数组存的是b,c数组元素的和,然后对d数组进行二分就可以了 代码如下(附注释): #include<iostream>#include<algorithm>#include<cstring>#include<stack>#include<que

hdu 1166 敌兵布阵(树状数组 or 线段树)

题意是求一个线段的和,在线段上可以进行加减的修改。 树状数组的模板题。 代码: #include <stdio.h>#include <string.h>const int maxn = 50000 + 1;int c[maxn];int n;int lowbit(int x){return x & -x;}void add(int x, int num){while