文章目录
- 前言
- 题目1:移除数组中指定的元素
- 题目描述
- 解题思路
- 方法1 :暴力法
- 方法2:双指针法
- 题目2:数组去重
- 题目描述
- 解题思路
- 双指针法
- 题目3:合并两个有序的数组
- 题目描述
- 解题思路
- 方法1:暴力破解法
- 方法2:从后往前
前言
通过有关顺序表的知识讲解,相信大家或多或少都对顺序表有一定的了解。
那么在本文中,我们将会给出几道有关于顺序表(个人觉得于数组的相关性较大)经典的代码练习题,并且总结一些做题的经验,呈现给大家。
题目1:移除数组中指定的元素
题目链接:移除元素 - LeetCode
题目描述
解题思路
方法1 :暴力法
相信很多人看到这道题的时候,会不自觉的这样想:我先遍历题目所给的数组,在遍历的过程中,将每个数组中的每个元素与题目所给的那个val进行比较。如果不相等的话,我就把那个元素赋值到我新建的数组中。
由于这个想法比较简单,这里我就不画图进行讲解了。
实现的代码如下:
//方法1:暴力法
#include<stdlib.h>
int removeElement(int* nums, int numsSize, int val) {//创建一个与题目所给数组一样大小的空间int* newnums = (int*)malloc(sizeof(int)*numsSize);if (newnums == NULL){perror("malloc fail");exit(1);}//开始进行删除数据int i = 0;int count = 0;while (i < numsSize){if (nums[i] != val){newnums[count++] = nums[i];}i++;}return count;
}
方法2:双指针法
相信经过上面的描述,已经对双指针的用法有了初步的感觉了!如果还不会的话,不用担心,本文后面的题目仍会用到双指针法的。
实现的代码如下:
int removeElement(int* nums, int numsSize, int val) {//创建两个指针,但对于数组来说下表的移动也可以相当是指针的移动int src = 0, dst = 0;while (src < numsSize){if (nums[src] != val){nums[src++] = nums[dst++];}else{src++;}}return dst;}
题目2:数组去重
题目链接:数组去重 - LeetCode
题目描述
解题思路
这题的难点在于原地删除重复出现的元素,这个就意味着我们无法像上面那道题一样创建新数组去完成了。
那该怎么办呢?在仔细看一下条件,题目还说了数组的元素是非严格递增排列的。但是我们有前面移除数组元素题目做铺垫,这两道题的共性都在于删除元素。
那我们可以先用双指针法来尝试做一下这道题!
这里你会发现,指针src就像一个侦察兵,dst指针就像一个大本营。当指针src发现前面有埋伏时,它就会跟大本营说,前面有埋伏,你不要过来,让我看看还有哪个地方时没有敌人的埋伏的。当发现没有埋伏是,大本营就会根据src传递的信息记录下这个没有埋伏的地方!
看到这里,你会发现:噢,双指针法真的能解决这个问题。但是你再仔细思考一下,如果数组是乱序的话,还能不能这样做?
很显然是不能的,因为dst指针指向的位置一旦被赋值之后,dst指针就会往下挪动一个位置。那假如,src在数组很后面的位置找到了dst之前那个位置的值,那就没有办法检测到了。
双指针法
代码实现:
//双指针法
int removeDuplicates(int* nums, int numsSize)
{int dst = 0, src = 1;while (src < numsSize){if (nums[dst] == nums[src]){//说明,src位置的元素是重复出现的。我们就要记录下来这个位置。//做法就是,我们可以先不动dst位置,等到值不一样的时候,再移动并赋值。src++;}else{nums[++dst] = nums[src++];}}return dst+1;
}
可能有的读者这里会问,能不能在nums[dst] == nums[src]的时候,将dst和src指针都移动一个位置。答案是不能!
自己画图就可以理解这一点了。
也许看到这里,你会说双指针法很好用!确实,它非常的好用!
题目3:合并两个有序的数组
题目链接:合并两个有序的数组 - LeetCode
题目描述
解题思路
按照题目的要求给了我们两个非递减顺序排列的数组。目的就是让我们合并它们,并且合并之后数组是按照非递减顺序排列的。
那该怎么做呢?我们在没有思路时,可以先去看一下题目给出的一些案例。不过我相信有一个方法是大家都能想到的,这里我姑且叫它暴力破解法
方法1:暴力破解法
将两个有序数组合并成一个数组之后,在使用排序算法,将它变成有序的!没错这个方法的确可行。
代码实现如下:
//思路:先将两个数组合并之后,再排序
#include<stdlib.h>
int compare_int(const void* x, const void* y)
{return *((int*)x) - *((int*)y);
}void merge(int* nums1, int nums1Size, int m, int* nums2, int nums2Size, int n) {//申请一块地址空间,用于存放两个数组合并之后的数组int* nums = (int*)malloc(sizeof(int) * (m + n));if (nums == NULL){perror("malloc fail");exit(1);}int count = 0;for (int i = 0; i < m; i++){nums[count++] = nums1[i];}for (int i = 0; i < n; i++){nums[count++] = nums2[i];}//这里使用qsort函数进行排序qsort(nums,m+n,sizeof(int),compare_int);}
方法2:从后往前
代码实现:
void merge(int* nums1, int nums1Size, int m, int* nums2, int nums2Size, int n) {int n1 = m -1 , n2 = n - 1;int end = n1 + n2 + 1;while(n1 >= 0 && n2 >= 0){if(nums1[n1] > nums2[n2]){nums1[end--] = nums1[n1--];}else{nums1[end--] = nums2[n2--];}}//循环退出之后,一定有个数组还未遍历完。//如果是nums1这个数组未遍历完,其实可以不用给它单独处理//因为,题目要求返回的是nums1//如果是nums2的话,那就要给它处理一下while(n2 >= 0){nums1[end--] = nums2[n2--];}//}}
到这里,我们习题就已经全部讲完了。
本文主要讲解了一种解题方法:双指针法,针对这个方法,我会还会再出题目的讲解的!
如果觉得本文讲的还不错的话,麻烦给偶点个赞吧!!!