中学网站建设 课设,定制高端网站建设,池州市网站建设,深圳网站网页制作#x1f680;write in front#x1f680; #x1f4dc;所属专栏#xff1a; 初阶数据结构 #x1f6f0;️博客主页#xff1a;睿睿的博客主页 #x1f6f0;️代码仓库#xff1a;#x1f389;VS2022_C语言仓库 #x1f3a1;您的点赞、关注、收藏、评论#xff0… write in front 所属专栏 初阶数据结构 ️博客主页睿睿的博客主页 ️代码仓库VS2022_C语言仓库 您的点赞、关注、收藏、评论是对我最大的激励和支持 关注我关注我关注我你们将会看到更多的优质内容 文章目录前言一.空间换时间的方式二.多指针方式总结前言 大家在处理数组相关的oj题时一般通过遍历的方式但是这样会导致时间复杂度非常的高。下面我来介绍一下通过空间换时间和双指针的方式减小时间复杂度
一.空间换时间的方式
栗子: 原地移除数组中所有的元素val要求时间复杂度为O(N)空间复杂度为O(1)。oj题 家人们刚开始做这题时很可能会通过遍历数组然后将后面的数字往前移这样就会导致时间复杂度非常高。 这个时候我们就可以通过牺牲空间节省时间的方式来降低时间复杂度。 通过创建一个新数组来保存保留的数据这样就通过牺牲空间节省了时间。但是这题需要空间复杂度为O1说明不能创建额外的n个空间那么我们该怎么办呢下面的双指针方式会告诉你如何去做可以先看看代码
void merge(int* nums1, int nums1Size, int m, int* nums2, int nums2Size, int n)
{int end1m-1,end2n-1,dstmn-1;while(end10end20){if(nums1[end1]nums2[end2]){nums1[dst--]nums1[end1--];}else{nums1[dst--]nums2[end2--];}}while(end20){nums1[dst--]nums2[end2--];}
}二.多指针方式 这里我们指的指针在数组里面可以用数字来代替因为数组是可以通过[]访问的但是后面链表所用的指针就是真的指针了。 多指针的使用是非常重要的方法但是非常依赖画图所以只要同学们多画图此类题目不会很难解决。 栗子 合并两个有序数组oj题 对于合并两个有序数组兄弟们很有可能将两个数组合并然后进行排序。然而这样编写的后果是时间复杂度会比较高。 我们创建一个新数组(牺牲空间)通过两个数字分别标记两个数组通过比较得到最终的排好序的数组。 然而这道题的数组空余部分是0所以我们要从后往前排序并且在原数组里排序这个时候也需要通过两个指针来标记。 void merge(int* nums1, int nums1Size, int m, int* nums2, int nums2Size, int n)
{int end1m-1,end2n-1,dstmn-1;while(end10end20){if(nums1[end1]nums2[end2]){nums1[dst--]nums1[end1--];}else{nums1[dst--]nums2[end2--];}}while(end20){nums1[dst--]nums2[end2--];}
}总结 总的来说这两种方法就是解决顺序表的主题思路。对于数据结构家人们一定不要空想要多通过画图解决问题。 更新不易辛苦各位小伙伴们动动小手三连走一走 ~ ~ ~ 你们真的对我很重要最后本文仍有许多不足之处欢迎各位认真读完文章的小伙伴们随时私信交流、批评指正 专栏订阅 每日一题 c语言学习 算法 智力题 初阶数据结构 更新不易辛苦各位小伙伴们动动小手三连走一走 ~ ~ ~ 你们真的对我很重要最后本文仍有许多不足之处欢迎各位认真读完文章的小伙伴们随时私信交流、批评指正
