力扣题解2848

大家好,欢迎来到无限大的频道。

今日继续给大家带来力扣题解。

题目描述(简单):

与车相交的点

给你一个下标从 0 开始的二维整数数组 nums 表示汽车停放在数轴上的坐标。对于任意下标 i,nums[i] = [starti, endi] ,其中 starti 是第 i 辆车的起点,endi 是第 i 辆车的终点。

返回数轴上被车 任意部分 覆盖的整数点的数目。

解题思路:

这道问题抽象就抽象在,读不懂题目要求干啥,也不明白举例是什么意思,得先把题目看懂。(我来中译中一下)

这个问题可以理解为在数轴上有多辆车,每辆车的停车区域用一个区间来表示,例如 nums[i] = [starti, endi] 表示第 i 辆车的起点为 starti,终点为 endi。我们需要计算在数轴上这些车的停车区域重叠部分所覆盖的整数点的总数。

具体来说,我们需要求出所有车辆停车区间内的整数点的总和,即使得某一点被多辆车的区间覆盖也只算一次。

示例说明:

假设车辆的区间如下:

  • 车1: [1, 3]

  • 车2: [2, 5]

  • 车3: [4, 6]

那么这些车辆覆盖的区间为:

  • 车1覆盖的整数点为 {1, 2, 3}

  • 车2覆盖的整数点为 {2, 3, 4, 5}

  • 车3覆盖的整数点为 {4, 5, 6}

所有被覆盖的整数点为 {1, 2, 3, 4, 5, 6},所以被覆盖的整数点总数为 6。

算法思路

  1. 合并区间:首先对所有区间进行合并,去掉重叠部分。

  2. 计算被覆盖的点:在合并之后计算每个区间中整数点的数量,即为 end - start + 1 的总和。

3.采用排序加贪心策略

参考代码:

// 定义一个结构体来表示区间
typedef struct {int start;int end;
} Interval;
​
// 比较函数用于排序
int compare(const void *a, const void *b) {Interval *intervalA = (Interval *)a;Interval *intervalB = (Interval *)b;return intervalA->start - intervalB->start;
}
​
int numberOfPoints(int** nums, int numsSize, int* numsColSize) {if (numsSize == 0) return 0;
​// 1. 创建一个 Interval 数组Interval* intervals = (Interval*)malloc(numsSize * sizeof(Interval));
​// 2. 将 nums 转换为 Interval 数组for (int i = 0; i < numsSize; i++) {intervals[i].start = nums[i][0];intervals[i].end = nums[i][1];}
​// 3. 排序区间qsort(intervals, numsSize, sizeof(Interval), compare);
​int totalPoints = 0;int currStart = intervals[0].start;int currEnd = intervals[0].end;
​// 4. 合并区间并计算覆盖的点for (int i = 1; i < numsSize; i++) {if (intervals[i].start <= currEnd) { // 如果有重叠// 扩大当前区间的结束点if (intervals[i].end > currEnd) {currEnd = intervals[i].end;}} else { // 如果没有重叠,计算当前区间的点数totalPoints += currEnd - currStart + 1;currStart = intervals[i].start;currEnd = intervals[i].end;}}
​// 添加最后一个区间的覆盖点totalPoints += currEnd - currStart + 1;
​// 释放内存free(intervals);
​return totalPoints;
}
​

时间复杂度:

1. 创建 Interval 数组:

   创建 Interval 数组的时间复杂度是 O(n),其中 n是输入的区间数量 `numsSize`。

2. 将 nums 转换为 Interval 数组:

   遍历所有区间并将其转换为 Interval 的时间复杂度同样是 O(n)。

3. 排序区间:

   使用 `qsort` 进行排序,排序的时间复杂度是 O(n log n)。

4. 合并区间并计算覆盖的点:

   遍历排好序的区间以合并并计算覆盖点的时间复杂度是 O(n)。

综上所述,主要的时间开销在于排序,因此整个 `numberOfPoints` 函数的时间复杂度为:

[O(n log n)]

 空间复杂度:

1. 存储 Interval 数组:

   创建存储 Interval 的数组需要 O(n)的额外空间。

2. 其他空间:

   在函数中使用的变量、指针等只占用常数空间 O(1),不随 n 的变化而变化。

因此,整个函数的空间复杂度主要依赖于存储 Interval 数组的开销,为:

[O(n)]

总结:

时间复杂度:(O(n log n))

空间复杂度:(O(n))​

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/424536.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

html+css+js网页设计 旅游 厦门旅游网10个页面

htmlcssjs网页设计 旅游 厦门旅游网10个页面 网页作品代码简单&#xff0c;可使用任意HTML辑软件&#xff08;如&#xff1a;Dreamweaver、HBuilder、Vscode 、Sublime 、Webstorm、Text 、Notepad 等任意html编辑软件进行运行及修改编辑等操作&#xff09;。 获取源码 1&am…

SpringBoot权限认证-Sa-Token的使用与详解

本文详细介绍了Sa-Token在Java项目中的使用方法&#xff0c;包括Sa-Token的基本概念、与其他权限框架的比较、基本语法和高级用法&#xff0c;并通过实例讲解了如何在项目中集成和使用Sa-Token。作为一款轻量级Java权限认证框架&#xff0c;Sa-Token在简化权限管理、提高开发效…

『功能项目』切换职业技能面板【49】

我们打开上一篇48切换职业面板的项目&#xff0c; 本章要做的事情是制作第二职业法师技能面板、第三职业面板并且完成切换 双击打开Canvas进入预制体空间 复制三个技能栏面板 重命名 设置第一技能栏 设置第二职业技能栏 设置第三职业技能栏 修改脚本&#xff1a;ChangeProfess…

FreeRTOS—任务通知

一&#xff0c;概念介绍 队列、信号量、事件组等IPC技术都需要创建一个中间对象进程之间通过这些中间对象进行通讯或同步。创建对象就需要分配内存&#xff0c;占用一定内存。 二&#xff0c;任务通知的特点&#xff1a; 一个任务或ISR向另外一个指定的任务发送通知&#xff0c…

PhpStudy下载安装使用学习

一、官网下载 官网地址&#xff1a;Windows版phpstudy下载 - 小皮面板(phpstudy)https://old.xp.cn/download.html 【首页】选择Windows版&#xff0c;进行下载 下载完成是一个压缩包的形式&#xff0c;解压得到一个.exe的执行文件&#xff0c;点击执行安装程序&#xff08;注…

Spring Boot环境下的学生读书笔记共享

第4章 系统设计 4.1系统结构设计 读书笔记共享平台的设计主要是为了满足用户的实际需求。 因此&#xff0c;它需要通过Internet实现&#xff0c;因此它必须具备硬件和软件基础。该平台最终可以通过科学技术和各种方式达到支持智能化的信息管理的目的。因此&#xff0c;它必须具…

数据结构——(java版)Map与Set

文章目录 二叉搜索树&#xff08;1&#xff09; 二叉搜索树的概念&#xff1a;&#xff08;2&#xff09;二叉搜索树的意义&#xff1a;&#xff08;3&#xff09;二叉搜索树的实现&#xff1a;实现的方法与属性实现二叉搜索树的查询&#xff1a;实现二叉搜索树的插入&#xff…

【Kubernetes笔记】为什么DNS解析会超时?

【Kubernetes笔记】为什么DNS解析会超时&#xff1f; 目录 1 问题背景2 产生后续的问题3 DNS 负缓存工作原理&#xff1a;4 如何解决和缓解 DNS 负缓存 4.1 减小负缓存 TTL4.2 重试机制4.3 减少 Pod 的频繁重启或调度4.4 使用 Headless Service4.5 手动刷新 DNS 缓存 5 总结 …

【Unity】 HTFramework框架(五十六)MarkdownText:支持运行时解析并显示Markdown文本

更新日期&#xff1a;2024年9月15日。 Github源码&#xff1a;[点我获取源码] Gitee源码&#xff1a;[点我获取源码] 索引 MarkdownText支持的Markdown语法标题强调文本表格嵌入图像超链接 使用MarkdownText设置项运行时属性解析使用ID模式嵌入图像 MarkdownText MarkdownText…

【Python机器学习】循环神经网络(RNN)——对RNN进行预测

目录 有状态性 双向RNN 编码向量 如果有一个经过训练的模型&#xff0c;接下来就可以对其进行预测&#xff1a; sample_1""" I hate that the dismal weather had me down for so long,when will it break! Ugh,when does happiness return? The sun is bl…

Neo4j图数据库

文章目录 一、Neo4J相关介绍1.为什么需要图数据库方案1&#xff1a;Google方案2&#xff1a;Facebook 2.特定和优势3.什么是Neo4j4.Neo4j数据模型图论基础属性图模型Neo4j的构建元素 5.软件安装 二、CQL语句1.CQL简介2.CREATE 命令3.MATCH 命令4.RETURN 子句5.MATCH和RETURN6.C…

Qt_显示类控件

目录 一、QLabel 1、QLabel属性介绍 2、textFormat文本格式 3、pixmap标签图片 3.1 resizeEvent 4、QFrame边框 5、alignment文本对齐 6、wordWrap自动换行 7、indent设置缩进 8、margin设置边距 9、buddy设置伙伴 二、QLCDNumber 1、QLCDNumber属性介绍 2、实…

SSM网上书店管理系统---附源码72542

目 录 摘要 1 绪论 1.1 研究背景及意义 1.2国内外研究现状 1.3系统开发的目标 1.4论文结构与章节安排 2 网上书店管理系统系统分析 2.1 可行性分析 2.1.1 技术可行性分析 2.1.2 经济可行性分析 2.1.3 操作可行性分析 2.2 系统功能分析 2.2.1 功能性分析 2.2.2 非…

【在Linux世界中追寻伟大的One Piece】网络命令|验证UDP

目录 1 -> Ping命令 2 -> Netstat命令 3 -> Pidof命令 4 -> 验证UDP-Windows作为client访问Linux 4.1 -> UDP client样例 1 -> Ping命令 Ping命令是一种网络诊断工具&#xff0c;它使用ICMP(Internet Control Message Protocol&#xff0c;互联网控制消…

音视频开发常见的开源项目汇总

FFmpeg 地址&#xff1a;https://ffmpeg.org/介绍&#xff1a;FFmpeg 是一个非常强大的开源多媒体框架&#xff0c;它可以用来处理视频和音频文件。它支持多种格式的转换、编码、解码、转码、流处理等。FFmpeg 包括了 libavformat、libavcodec、libavutil、libswscale、libpos…

数据结构基础讲解(八)——树和二叉树专项练习(上)

本文数据结构讲解参考书目&#xff1a; 通过网盘分享的文件&#xff1a;数据结构 C语言版.pdf 链接: https://pan.baidu.com/s/159y_QTbXqpMhNCNP_Fls9g?pwdze8e 提取码: ze8e 数据结构基础讲解&#xff08;七&#xff09;——数组和广义表专项练习-CSDN博客 个人主页&#x…

IDEA 常用配置和开发插件

件市场中搜索并安装“Git Integration”插件。 一、前言 在本篇文章中我会为大家总结一些我自己常用的配置和开发插件&#xff0c;此外也给大家提供一个建议&#xff0c;可以根据自己的项目需求和个人偏好选择适合的插件。另外&#xff0c;IDEA 也在不断更新&#xff0c;可能会…

C++进阶 二叉搜索树的讲解

二叉搜索树的概念 二叉搜索树又称为二叉排序树。 二叉搜索树的性质 若它的左子树不为空&#xff0c;则左子树上所有结点的值都小于等于根结点的值若它的右子树不为空&#xff0c;则右子树上所有结点的值都大于等于根结点的值它的左右子树也分别为二叉搜索树二叉搜索树中可以支持…

Geneformer AI 模型,有限数据也能解锁基因网络

目录 类似于 BERT 的单单元数据参考模型 NVIDIA Clara 工具组合用于药物研发 用于疾病建模的基础 AI 模型 Geneformer 是最近推出的 和功能强大的 AI 模型&#xff0c;可以通过从大量单细胞转录组数据中进行迁移学习来学习基因网络动力学和相互作用。借助此工具&#xff0c;…

尚品汇-订单拆单、支付宝关闭交易、关闭过期订单整合(五十)

目录&#xff1a; &#xff08;1&#xff09;拆单接口 &#xff08;2&#xff09;取消订单业务补充关闭支付记录 &#xff08;3&#xff09;支付宝关闭交易 &#xff08;4&#xff09;查询支付交易记录 &#xff08;5&#xff09;PaymentFeignClient 远程接口 &#xff08…