当前位置: 首页 > news >正文

【数据结构】面试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

目录 一&#xff1a;移除元素 思路&#xff1a; 二&#xff1a;删除有序数组中的重复项 思路&#xff1a; 三&#xff1a;合并两个有序数组 思路1&#xff1a; 什么&#xff1f;你不知道qsort&#xff08;&#xff09; 思路2&#xff1a; 一&#xff1a;移除元素 27. 移…...

LibreOffice编辑excel文档如何在单元格中输入手动换行符

用WPS编辑excel文档的时候&#xff0c;要在单元格中输入手动换行符&#xff0c;可以先按住Alt键&#xff0c;然后回车。 而用LibreOffice编辑excel文档&#xff0c;要在单元格中输入手动换行符&#xff0c;可以先按住Ctrl键&#xff0c;然后回车。例如&#xff1a;...

ideaSSM在线商务管理系统VS开发mysql数据库web结构java编程计算机网页源码maven项目

一、源码特点 SSM 在线商务管理系统是一套完善的信息管理系统&#xff0c;结合SSM框架和bootstrap完成本系统&#xff0c;对理解JSP java编程开发语言有帮助系统采用SSM框架&#xff08;MVC模式开发&#xff09;&#xff0c;系统具有完整的源代码 和数据库&#xff0c;系统主…...

数据结构 | 顺序表专题

数据结构 | 顺序表专题 文章目录 数据结构 | 顺序表专题课前准备1. 目标2. 需要的储备知识3. 数据结构相关概念 开始顺序表1、顺序表的概念及结构2、顺序表分类3、动态顺序表的实现初始化顺序表打印顺序表内存容量的检查顺序表的尾插顺序表的尾删顺序表的头插顺序表的头删在顺序…...

C++可视化 有穷自动机NFA 有穷自动机DFA

一、项目介绍 根据正则表达式,可视化显示NFA&#xff0c;DFA&#xff1b;词法分析程序 二、项目展示...

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> 效果&#xff1a; 3.通过npm下载并复制…...

MySQL安全基线检查

目录 安全基线检查基础知识MySQL 的安全基线检查MySQL 更严格的一些基线检查内容一、安全基线检查基础知识 1、安全基线的定义: 安全基线是一个信息系统的最小安全保证,即该信息系统最基本需要满足的安全要求。它是在安全付出成本与所能够承受的安全风险之间进行平衡的合理…...

Unity主程如何做好游戏项目管理

前言 很多小伙伴最近在面试或者考虑跳槽,可能工作了3~5年了想涨薪或想做技术总监或主程, 可自己还是个雏&#xff0c;没有做过项目技术管理&#xff0c;怎么办&#xff1f;今天我给大家梳理一下作为一个技术总监或主程你应该如何带好一个游戏项目&#xff0c;做好技术管理。接…...

103.linux5.15.198 编译 firefly-rk3399(2)

1. 平台&#xff1a; rk3399 firefly 2g16g 2. 内核&#xff1a;linux5.15.136 &#xff08;从内核镜像网站下载&#xff09; 3. 交叉编译工具 gcc version 7.5.0 (Ubuntu/Linaro 7.5.0-3ubuntu1~18.04) 4. 宿主机&#xff1a;ubuntu18.04 5. 需要的素材和资料&#xff…...

如何从Android手机上轻松恢复误删除的短信 ?

当您使用 Android 手机时&#xff0c;您可能会误删除一些 Android 短信。如果这些消息对您很重要&#xff0c;您可能想要恢复它们。在这种情况下&#xff0c;您可以尝试使用U1tData安卓数据恢复&#xff08;奇客软件&#xff09; 来完成这项工作。这篇文章将向您展示更多信息。…...

毅速丨金属3D打印能替代传统制造吗?

金属3D打印技术已经逐渐被很多行业认可和应用&#xff0c;但是目前&#xff0c;金属3D打印多数被作为传统制造技术的一种补充&#xff0c;暂时还不能完全替代传统制造。 金属3D打印使用的是金属粉末进行选择性激光烧结&#xff0c;打印时在成型缸里铺上金属粉末&#xff0c;打印…...

21个新的ChatGPT应用

自从GPT有了图识别功能后变的更加强大&#xff0c;特别是ChatGPT的视觉技术&#xff0c;为我们提供了无数的可能性。本文将深入探讨这21种应用场景&#xff0c;帮助理解其在日常生活和工作中的实际价值。 生活助手&#xff1a;为日常生活增添色彩 健身计划定制&#xff1a;你…...

【通信原理】第二章|确知信号

前言 那么这里博主先安利一些干货满满的专栏了&#xff01; 首先是博主的高质量博客的汇总&#xff0c;这个专栏里面的博客&#xff0c;都是博主最最用心写的一部分&#xff0c;干货满满&#xff0c;希望对大家有帮助。 高质量博客汇总 文章目录 前言 第二章 确知信号1. 确知…...

【JVM】类加载器

【JVM】类加载器 文章目录 【JVM】类加载器0. 类加载器概述1. 类加载器的分类1.1 启动类加载器1.2 Java中的默认类加载器1.2.1 扩展类加载器1.2.2 应用程序类加载器 2. 双亲委派机制2.1 类的双亲委派机制是什么&#xff1f;2.2 打破双亲委派机制2.2.1 自定义类加载器2.2.2 线程…...

利用Excel支持JUnit参数化测试

在JUnit里面&#xff0c;可以使用CsvFileSource读取csv文件进行参数化测试&#xff0c;可是CSV文件不支持格式&#xff0c;编辑颇为麻烦&#xff0c;尤其是多次编辑&#xff0c;因此自然想到是否可以使用Excel文件&#xff0c;可以有各种格式&#xff0c;支持各类数据。 最新开…...

第三章 SysML入门|系统建模语言SysML实用指南学习

仅供个人学习记录 UML与SysML的联系 可以稍微参考UML与SysML的联系 UML&#xff08;统一建模语言&#xff09;和SysML&#xff08;系统建模语言&#xff09;是两种与建模相关的语言&#xff0c;它们之间存在联系和区别。 SysML的图分类如下图所示。 SysML 图概述 这里只…...

敏捷开发框架Scrum-概述

如果你是一个程序员&#xff0c;可能会觉得这是个程序开发框架。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&#xff0c;来实现数据读取、清洗、计算和入库。 如下图所示SQL是最高层级的…...

文心一言 VS 讯飞星火 VS chatgpt (123)-- 算法导论10.4 4题

四、用go语言&#xff0c;对于一个含 n个结点的任意有根树&#xff0c;写出一个 O(n)时间的过程&#xff0c;输出其所有关键字该树以左孩子右兄弟表示法存储。 文心一言&#xff1a; 在计算机科学中&#xff0c;左孩子右兄弟表示法是一种用于表示树状结构的方法&#xff0c;其…...

golang循环变量捕获问题​​

在 Go 语言中&#xff0c;当在循环中启动协程&#xff08;goroutine&#xff09;时&#xff0c;如果在协程闭包中直接引用循环变量&#xff0c;可能会遇到一个常见的陷阱 - ​​循环变量捕获问题​​。让我详细解释一下&#xff1a; 问题背景 看这个代码片段&#xff1a; fo…...

学校招生小程序源码介绍

基于ThinkPHPFastAdminUniApp开发的学校招生小程序源码&#xff0c;专为学校招生场景量身打造&#xff0c;功能实用且操作便捷。 从技术架构来看&#xff0c;ThinkPHP提供稳定可靠的后台服务&#xff0c;FastAdmin加速开发流程&#xff0c;UniApp则保障小程序在多端有良好的兼…...

DBAPI如何优雅的获取单条数据

API如何优雅的获取单条数据 案例一 对于查询类API&#xff0c;查询的是单条数据&#xff0c;比如根据主键ID查询用户信息&#xff0c;sql如下&#xff1a; select id, name, age from user where id #{id}API默认返回的数据格式是多条的&#xff0c;如下&#xff1a; {&qu…...

爬虫基础学习day2

# 爬虫设计领域 工商&#xff1a;企查查、天眼查短视频&#xff1a;抖音、快手、西瓜 ---> 飞瓜电商&#xff1a;京东、淘宝、聚美优品、亚马逊 ---> 分析店铺经营决策标题、排名航空&#xff1a;抓取所有航空公司价格 ---> 去哪儿自媒体&#xff1a;采集自媒体数据进…...

JVM暂停(Stop-The-World,STW)的原因分类及对应排查方案

JVM暂停(Stop-The-World,STW)的完整原因分类及对应排查方案,结合JVM运行机制和常见故障场景整理而成: 一、GC相关暂停​​ 1. ​​安全点(Safepoint)阻塞​​ ​​现象​​:JVM暂停但无GC日志,日志显示No GCs detected。​​原因​​:JVM等待所有线程进入安全点(如…...

学校时钟系统,标准考场时钟系统,AI亮相2025高考,赛思时钟系统为教育公平筑起“精准防线”

2025年#高考 将在近日拉开帷幕&#xff0c;#AI 监考一度冲上热搜。当AI深度融入高考&#xff0c;#时间同步 不再是辅助功能&#xff0c;而是决定AI监考系统成败的“生命线”。 AI亮相2025高考&#xff0c;40种异常行为0.5秒精准识别 2025年高考即将拉开帷幕&#xff0c;江西、…...

云原生玩法三问:构建自定义开发环境

云原生玩法三问&#xff1a;构建自定义开发环境 引言 临时运维一个古董项目&#xff0c;无文档&#xff0c;无环境&#xff0c;无交接人&#xff0c;俗称三无。 运行设备的环境老&#xff0c;本地环境版本高&#xff0c;ssh不过去。正好最近对 腾讯出品的云原生 cnb 感兴趣&…...

初探Service服务发现机制

1.Service简介 Service是将运行在一组Pod上的应用程序发布为网络服务的抽象方法。 主要功能&#xff1a;服务发现和负载均衡。 Service类型的包括ClusterIP类型、NodePort类型、LoadBalancer类型、ExternalName类型 2.Endpoints简介 Endpoints是一种Kubernetes资源&#xf…...

JavaScript基础-API 和 Web API

在学习JavaScript的过程中&#xff0c;理解API&#xff08;应用程序接口&#xff09;和Web API的概念及其应用是非常重要的。这些工具极大地扩展了JavaScript的功能&#xff0c;使得开发者能够创建出功能丰富、交互性强的Web应用程序。本文将深入探讨JavaScript中的API与Web AP…...

LLMs 系列实操科普(1)

写在前面&#xff1a; 本期内容我们继续 Andrej Karpathy 的《How I use LLMs》讲座内容&#xff0c;原视频时长 ~130 分钟&#xff0c;以实操演示主流的一些 LLMs 的使用&#xff0c;由于涉及到实操&#xff0c;实际上并不适合以文字整理&#xff0c;但还是决定尽量整理一份笔…...