【数据结构】面试OJ题——时间复杂度2
目录
一:移除元素
思路:
二:删除有序数组中的重复项
思路:
三:合并两个有序数组
思路1:
什么?你不知道qsort()
思路2:
一:移除元素
27. 移除元素 - 力扣(LeetCode)
给你一个数组
nums和一个值val,你需要 原地 移除所有数值等于val的元素,并返回移除后数组的新长度。不要使用额外的数组空间,你必须仅使用
O(1)额外空间并 原地 修改输入数组。元素的顺序可以改变。你不需要考虑数组中超出新长度后面的元素。


思路:
使用快慢指针 !
定义两个变量,一个用来遍历数组查看是否有和val值相等的,一个用来记录下来不等于val值的,放入数组中;
//27移除元素int removeElement(int* nums, int numsSize, int val)
{int src = 0; //遍历 快指针int dst = 0; //记录有效值 慢指针
//另外一种实现//for (src; src < numsSize; ++src)//{// if (nums[src] != val)// {// nums[dst++] = nums[src];// }//}while (src < numsSize){if (nums[src] != val){nums[dst++] = nums[src++]; //将有效值存到有效范围}else{src++;}}return dst;
}
int main()
{int nums[] = { 0, 1, 2, 2, 3, 0, 4, 2 };int numsSize = sizeof(nums) / sizeof(nums[0]);int val = 2;int dst = removeElement(nums, numsSize, val);printf("%d\n", dst); //vs调试写的,及以下可忽略while (dst--){printf("%d ", nums[dst]);}return 0;
}
时间复杂度:O(n),其中 n 为序列的长度。我们只需要遍历该序列至多两次。
空间复杂度:O(1)。我们只需要常数的空间保存若干变量。
二:删除有序数组中的重复项
26. 删除有序数组中的重复项 - 力扣(LeetCode)

思路:
这里依旧可以使用快慢指针;
我这里还多定义了一个遍量,拿来记录有效值;不过显得冗余,但非常容易理解;
最后一步是将最后一个不同值记录下来;
从图可以看到dst走到最后一个元素时,此元素也应该记录;
int removeDuplicates(int* nums, int numsSize) {int src = 1; //快指针int dst = 0; //慢指针int k = 0; //记录有效值while (src < numsSize){if (nums[src] != nums[dst]){nums[k++] = nums[dst++]; //将慢指针值放入有效范围中src++;}else{src++; dst++;}}nums[k++] = nums[dst]; //将最后不同的值放入return k;
}
刚刚也说了,可以对此想法进行优化
我们可以发现时删除重复项,也就说第一个元素该值都是有效的,可以定义变量从1开始;
然后定义遍历变量就行for循环,前后比较,将有效值放到有效位置中
int removeDuplicates(int* nums, int numsSize){int index = 1; //第一个值默认有效for(int i =1;i<numsSize;i++) {if(nums[i-1] != nums[i]) //前后比较{nums[index++] = nums[i]; //将快指针值放入有效位置中}}return index;
}
三:合并两个有序数组
88. 合并两个有序数组 - 力扣(LeetCode)

思路1:
题目说了 数组1是可以包容数组2进去的,我们可以直接将数组2有效值放入数组1最后一个有效值后,先将两个数组值合并在数组1中,再直接qsort排序即可啦

int compare(const void* e1, const void* e2)
{return *(int*)e1 - *(int*)e2;
}
void merge(int* nums1, int nums1Size, int m, int* nums2, int nums2Size, int n){//合并两个数组int j =m;for(int i =0;i<n;i++){nums1[j++] = nums2[i];}qsort(nums1,nums1Size,sizeof(nums1[0]),compare);
}
什么?你不知道qsort()
欧克,锁定往期文章【C语言】进阶——指针_敷敷_的博客-CSDN博客
里面详细讲述了关于 qsort()的使用哦,
思路2:
我们换一种方式,不使用qsort,
void merge(int* nums1, int nums1Size, int m, int* nums2, int nums2Size, int n) {// end1、end2:分别标记nums1 和 nums2最后一个有效元素位置// end标记nums1的末尾,因为nums1和nums2中的元素从后往前往nums1中存放// ,否则会存在数据覆盖int end1 = m - 1;int end2 = n - 1;int index = m + n - 1;// 从后往前遍历,将num1或者nums2中较大的元素往num1中end位置搬移// 直到将num1或者num2中有效元素全部搬移完while (end1 >= 0 && end2 >= 0){if (nums1[end1] > nums2[end2]){nums1[index--] = nums1[end1--];}else{nums1[index--] = nums2[end2--];}}// num2中的元素可能没有搬移完,将剩余的元素继续往nums1中搬移while (end2 >= 0){nums1[index--] = nums2[end2--];}// num1中剩余元素没有搬移完 ---不用管了,因为num1中剩余的元素本来就在num1中
}

相关文章:
【数据结构】面试OJ题——时间复杂度2
目录 一:移除元素 思路: 二:删除有序数组中的重复项 思路: 三:合并两个有序数组 思路1: 什么?你不知道qsort() 思路2: 一:移除元素 27. 移…...
LibreOffice编辑excel文档如何在单元格中输入手动换行符
用WPS编辑excel文档的时候,要在单元格中输入手动换行符,可以先按住Alt键,然后回车。 而用LibreOffice编辑excel文档,要在单元格中输入手动换行符,可以先按住Ctrl键,然后回车。例如:...
ideaSSM在线商务管理系统VS开发mysql数据库web结构java编程计算机网页源码maven项目
一、源码特点 SSM 在线商务管理系统是一套完善的信息管理系统,结合SSM框架和bootstrap完成本系统,对理解JSP java编程开发语言有帮助系统采用SSM框架(MVC模式开发),系统具有完整的源代码 和数据库,系统主…...
数据结构 | 顺序表专题
数据结构 | 顺序表专题 文章目录 数据结构 | 顺序表专题课前准备1. 目标2. 需要的储备知识3. 数据结构相关概念 开始顺序表1、顺序表的概念及结构2、顺序表分类3、动态顺序表的实现初始化顺序表打印顺序表内存容量的检查顺序表的尾插顺序表的尾删顺序表的头插顺序表的头删在顺序…...
C++可视化 有穷自动机NFA 有穷自动机DFA
一、项目介绍 根据正则表达式,可视化显示NFA,DFA;词法分析程序 二、项目展示...
vite vue3 ts 使用sass 设置样式变量 和重置默认样式
1.安装scss 样式支持依赖 yarn add -D sass 2.使用sass <div><!-- 测试使用sass --><h1>测试使用sass</h1> </div><style scope lang"scss"> div {h1 {color: red;} } </style> 效果: 3.通过npm下载并复制…...
MySQL安全基线检查
目录 安全基线检查基础知识MySQL 的安全基线检查MySQL 更严格的一些基线检查内容一、安全基线检查基础知识 1、安全基线的定义: 安全基线是一个信息系统的最小安全保证,即该信息系统最基本需要满足的安全要求。它是在安全付出成本与所能够承受的安全风险之间进行平衡的合理…...
Unity主程如何做好游戏项目管理
前言 很多小伙伴最近在面试或者考虑跳槽,可能工作了3~5年了想涨薪或想做技术总监或主程, 可自己还是个雏,没有做过项目技术管理,怎么办?今天我给大家梳理一下作为一个技术总监或主程你应该如何带好一个游戏项目,做好技术管理。接…...
103.linux5.15.198 编译 firefly-rk3399(2)
1. 平台: rk3399 firefly 2g16g 2. 内核:linux5.15.136 (从内核镜像网站下载) 3. 交叉编译工具 gcc version 7.5.0 (Ubuntu/Linaro 7.5.0-3ubuntu1~18.04) 4. 宿主机:ubuntu18.04 5. 需要的素材和资料ÿ…...
如何从Android手机上轻松恢复误删除的短信 ?
当您使用 Android 手机时,您可能会误删除一些 Android 短信。如果这些消息对您很重要,您可能想要恢复它们。在这种情况下,您可以尝试使用U1tData安卓数据恢复(奇客软件) 来完成这项工作。这篇文章将向您展示更多信息。…...
毅速丨金属3D打印能替代传统制造吗?
金属3D打印技术已经逐渐被很多行业认可和应用,但是目前,金属3D打印多数被作为传统制造技术的一种补充,暂时还不能完全替代传统制造。 金属3D打印使用的是金属粉末进行选择性激光烧结,打印时在成型缸里铺上金属粉末,打印…...
21个新的ChatGPT应用
自从GPT有了图识别功能后变的更加强大,特别是ChatGPT的视觉技术,为我们提供了无数的可能性。本文将深入探讨这21种应用场景,帮助理解其在日常生活和工作中的实际价值。 生活助手:为日常生活增添色彩 健身计划定制:你…...
【通信原理】第二章|确知信号
前言 那么这里博主先安利一些干货满满的专栏了! 首先是博主的高质量博客的汇总,这个专栏里面的博客,都是博主最最用心写的一部分,干货满满,希望对大家有帮助。 高质量博客汇总 文章目录 前言 第二章 确知信号1. 确知…...
【JVM】类加载器
【JVM】类加载器 文章目录 【JVM】类加载器0. 类加载器概述1. 类加载器的分类1.1 启动类加载器1.2 Java中的默认类加载器1.2.1 扩展类加载器1.2.2 应用程序类加载器 2. 双亲委派机制2.1 类的双亲委派机制是什么?2.2 打破双亲委派机制2.2.1 自定义类加载器2.2.2 线程…...
利用Excel支持JUnit参数化测试
在JUnit里面,可以使用CsvFileSource读取csv文件进行参数化测试,可是CSV文件不支持格式,编辑颇为麻烦,尤其是多次编辑,因此自然想到是否可以使用Excel文件,可以有各种格式,支持各类数据。 最新开…...
第三章 SysML入门|系统建模语言SysML实用指南学习
仅供个人学习记录 UML与SysML的联系 可以稍微参考UML与SysML的联系 UML(统一建模语言)和SysML(系统建模语言)是两种与建模相关的语言,它们之间存在联系和区别。 SysML的图分类如下图所示。 SysML 图概述 这里只…...
敏捷开发框架Scrum-概述
如果你是一个程序员,可能会觉得这是个程序开发框架。Scrum是一个敏捷开发框架。我们可以把Scrum理解成一个团队一次完成一小部分工作的方式。这种方式通过不断的实验和反馈循环来学习和改进。Scrum可以帮助团队以协作的方式逐步交付价值。 Scrum框架由一个Scrum团队…...
Hafnium启动过程分析
安全之安全(security)博客目录导读 目录 一、在安全世界中加载Hafnium和安全分区 二、通过TF-A启动 1、SP manifests 2、安全分区包 3、描述安全分区...
0基础学习PyFlink——使用Table API实现SQL功能
大纲 Souceschemadescriptor Sinkschemadescriptor Execute完整代码参考资料 《0基础学习PyFlink——使用PyFlink的Sink将结果输出到Mysql》一文中,我们讲到如何通过定义Souce、Sink和Execute三个SQL,来实现数据读取、清洗、计算和入库。 如下图所示SQL是最高层级的…...
文心一言 VS 讯飞星火 VS chatgpt (123)-- 算法导论10.4 4题
四、用go语言,对于一个含 n个结点的任意有根树,写出一个 O(n)时间的过程,输出其所有关键字该树以左孩子右兄弟表示法存储。 文心一言: 在计算机科学中,左孩子右兄弟表示法是一种用于表示树状结构的方法,其…...
[2025CVPR]DeepVideo-R1:基于难度感知回归GRPO的视频强化微调框架详解
突破视频大语言模型推理瓶颈,在多个视频基准上实现SOTA性能 一、核心问题与创新亮点 1.1 GRPO在视频任务中的两大挑战 安全措施依赖问题 GRPO使用min和clip函数限制策略更新幅度,导致: 梯度抑制:当新旧策略差异过大时梯度消失收敛困难:策略无法充分优化# 传统GRPO的梯…...
label-studio的使用教程(导入本地路径)
文章目录 1. 准备环境2. 脚本启动2.1 Windows2.2 Linux 3. 安装label-studio机器学习后端3.1 pip安装(推荐)3.2 GitHub仓库安装 4. 后端配置4.1 yolo环境4.2 引入后端模型4.3 修改脚本4.4 启动后端 5. 标注工程5.1 创建工程5.2 配置图片路径5.3 配置工程类型标签5.4 配置模型5.…...
线程与协程
1. 线程与协程 1.1. “函数调用级别”的切换、上下文切换 1. 函数调用级别的切换 “函数调用级别的切换”是指:像函数调用/返回一样轻量地完成任务切换。 举例说明: 当你在程序中写一个函数调用: funcA() 然后 funcA 执行完后返回&…...
iPhone密码忘记了办?iPhoneUnlocker,iPhone解锁工具Aiseesoft iPhone Unlocker 高级注册版分享
平时用 iPhone 的时候,难免会碰到解锁的麻烦事。比如密码忘了、人脸识别 / 指纹识别突然不灵,或者买了二手 iPhone 却被原来的 iCloud 账号锁住,这时候就需要靠谱的解锁工具来帮忙了。Aiseesoft iPhone Unlocker 就是专门解决这些问题的软件&…...
Java多线程实现之Callable接口深度解析
Java多线程实现之Callable接口深度解析 一、Callable接口概述1.1 接口定义1.2 与Runnable接口的对比1.3 Future接口与FutureTask类 二、Callable接口的基本使用方法2.1 传统方式实现Callable接口2.2 使用Lambda表达式简化Callable实现2.3 使用FutureTask类执行Callable任务 三、…...
智能分布式爬虫的数据处理流水线优化:基于深度强化学习的数据质量控制
在数字化浪潮席卷全球的今天,数据已成为企业和研究机构的核心资产。智能分布式爬虫作为高效的数据采集工具,在大规模数据获取中发挥着关键作用。然而,传统的数据处理流水线在面对复杂多变的网络环境和海量异构数据时,常出现数据质…...
深度学习之模型压缩三驾马车:模型剪枝、模型量化、知识蒸馏
一、引言 在深度学习中,我们训练出的神经网络往往非常庞大(比如像 ResNet、YOLOv8、Vision Transformer),虽然精度很高,但“太重”了,运行起来很慢,占用内存大,不适合部署到手机、摄…...
小木的算法日记-多叉树的递归/层序遍历
🌲 从二叉树到森林:一文彻底搞懂多叉树遍历的艺术 🚀 引言 你好,未来的算法大神! 在数据结构的世界里,“树”无疑是最核心、最迷人的概念之一。我们中的大多数人都是从 二叉树 开始入门的,它…...
【UE5 C++】通过文件对话框获取选择文件的路径
目录 效果 步骤 源码 效果 步骤 1. 在“xxx.Build.cs”中添加需要使用的模块 ,这里主要使用“DesktopPlatform”模块 2. 添加后闭UE编辑器,右键点击 .uproject 文件,选择 "Generate Visual Studio project files",重…...
实战设计模式之模板方法模式
概述 模板方法模式定义了一个操作中的算法骨架,并将某些步骤延迟到子类中实现。模板方法使得子类可以在不改变算法结构的前提下,重新定义算法中的某些步骤。简单来说,就是在一个方法中定义了要执行的步骤顺序或算法框架,但允许子类…...
