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