【数据结构-初阶】顺序表相关习题
🎈主页传送门:良木生香
🔥个人专栏:《C语言》 《数据结构-初阶》 《程序设计》
🌟人为善,福随未至,祸已远行;人为恶,祸虽未至,福已远离
上期回顾：在上一篇文章中（【数据结构-初阶】详解线性表(1)---顺序表），我们详细介绍了线性表系列第一种数据结构---顺序表，这个数据结构是以数组为底建立的，也学习了如何用线性表进行增删查改的操作，那么我们今天就用顺序表进行解题~~~
题目一：移除元素
这是题目链接：27.移除元素，下面是具体的题目与示例：
由题意知,这道题是想让我们将数组中值为val的元素删除,我们能怎么做呢?
创建新的数组?那不行,题目已经要求我们只能在原地进行操作了,就意味着不能创建新的数组来进行辅助
那该怎么办呢?简单,我们只需用上算法中最基础的---双指针算法了
我们用双指针,不一定用真的指针指向某个元素,有时也可以用下标,讲究的是一种算法思想,并没有一定的形式
我们用两个指针,刚开始都同事之下那个num数组的第一个元素,随后将其中一个指针用于遍历数组,如果两个指针指向的内容不相同,那就将内容进行交换,两个指针同时向后移动一位;如果相同,那就只有遍历的指针移动,下面是示意图:
这时候我们只用在交换的同时用一个变量记录一下,就可以得到数组中值不为val的元素个数了,下面是在平台上的具体代码:
void swap(int* a,int* b) //创建辅助函数,用于交换两个数字 { int temp=0; temp = *a; *a = *b; *b = temp; } int removeElement(int* nums, int numsSize, int val) { int* cur=nums; int* dest = nums; int count=0; while(cur<nums+numsSize) { if(*cur != val) { swap(cur,dest); dest++; count++; } cur++; } return count; }要注意的是,我们在写交换函数的时候,传入的是地址,不是值,只有传值才能改变元素的值
下面是运行结果:
这是第一道题的题解~~~~
题目二：删除数组中的重复项
这是题目链接：26. 删除有序数组中的重复项，下面是具体的题目：
由题意知，这道题是想让我们将数组中重复的元素删除，同样的不能创建新的数组，那就继续使用双指针算法：用两个指针，dest与cur,如果*dest !=*cur,那就交换*dest与*cur的值,两者同时++即可,如果两者指向的元素相等,那就只有cur++,,dest保持不变
示意图如下:
以此类推,最后可推出示例的0,1,2,3,4,....,下面是我在平台上提交的代码:
int removeDuplicates(int* nums, int numsSize) { //这道题可以用双指针的方法 int* dest = nums; int* cur = nums+1; while(cur<nums+numsSize){ if(*dest!=*cur){ dest++; *dest = *cur; } cur++; } return dest-nums+1; }运行结果为:
题目三：合并两个有序数组
这是题目链接：88. 合并两个有序数组，下面是具体题目：
这道题就是想让我们将nums2放到num1里面,然后在对整个nums1进行排序
我们可以先将nums2放到nums1的末尾,再排序,这样确实可以达到目的,时间复杂度是O(n),但是这样就不能达到进阶的要求了,我们还能怎么做呢?小意思,我们可以从nums1最后的地方开始放进去,用三个指针,一个指向nums1非0元素的最后一个元素,一个指向nums1的末尾,一个指向nums2的末尾,如下面的的视频所示:
下面是具体的代码:
void merge(int* nums1, int nums1Size, int m, int* nums2, int nums2Size, int n) { int* p1 = nums1+m-1; int* p2 = nums2+n-1; int* p3 = nums1+m+n-1; while(p1>=nums1&&p2>=nums2) { if(*p1>*p2) { *p3-- = * p1--; } else *p3-- = *p2--; } while(p2>=nums2) { *p3-- = *p2--; } }这是运行结果:
那么以上就是顺序表的几道简单算法题的题解啦,感谢大佬们的阅读~~~
文章是自己写的哈，有什么描述不对的、不恰当的地方，恳请大佬指正，看到后会第一时间修改，感谢您的阅读。
