LeetCode链接:【27. 移除元素】
题目分析:
题目的大概意思就是给你一个数组和一个整数val要求你把数组中等于val的值给移除掉,并且返回移除后的数组长度。
当我们不考虑题目限制的情况下,最容易想到的思路是:我们可以遍历一遍数组把不等于val的元素全部拷贝到另外一个数组中,同时统计元素个数。
但是题目要求在原来的数组中移除元素,所以我们只能想办法把不等于val的元素统统移动到数组前面并且返回数组前面不等于val的元素个数。
问题又来了?我们怎么把等于val和不等于val的元素进行移动呢?
方法1:
我们可以想到用 【双指针法】两个指针开始都指向数组第一个元素,一个叫left,一个叫right;
如果指针right指向的元素等于val,指针right就往后面走一步,指针left不动,
如果指针right指向的元素不等于val,指针right就把所指向的元素赋值给指针left,指针left和指针right都往后走一步,直到指针right走到数组末端。
这样就把数组中不等于val的元素移动到前面,最后left就是不等于val元素的个数,直接返回left的值即可。
图片分析过程如下:
代码实现如下:
int removeElement(int* nums, int numsSize, int val){ int left=0; int right=0; while(right<numsSize) { //如果等于val,left不动,right往后走一步 if(nums[right]==val) { right++; } //如果不等于val,把right的值赋值给left, //同时left和right都往后走一步 else { nums[left]=nums[right]; left++; right++; } } return left; }
方法2:
这个方法是对方法1的优化,一个指针start指向第一个元素,一个指针end指向最后一个元素;
如果指针start等于val就和指针end进行交换元素,并且指针end自减1,指针start不动
如果指针start不等于val,指针start自增1,指针end不动,直到start和end相等。
图片分析如下:
代码实现如下:
int removeElement(int* nums, int numsSize, int val){ int start=0; int end=numsSize-1; while(start<=end) { //如果start的值等于val,就把end的值赋值给start //并且start不动,end往前面走一步 if(nums[start]==val) { nums[start]=nums[end]; end--; } //如果start的值不等于val,end不动,start往后走一步 else { start++; } } return start; }
LeetCode链接:【26. 删除有序数组中的重复项】
这个思路和上面那道题差不多,都是要在原数组中移除元素,所以可以用【双指针法】来解决:
一个指针i指向第一个元素,一个指针j指向第二个元素;
如果两指针的元素不相等,两个指针就往后面加1,
如果两指针的元素相等,指针j就往后面找和i不相等的元素,找到了就赋值给i的下一位元素,然后接着对比两个指针的元素,直到j走到数组末端。
过程分析如下:
代码实现如下:
int removeDuplicates(int* nums, int numsSize){ int i=0; int j=1; //给两个指针, if(numsSize==0) { return 0; } while(j<numsSize) { //不相等两个指针就往后面加1 if(nums[j]!=nums[i]) { i++; j++; } //相等j就往后面找到和i不相等的元素 else { while(j<numsSize) { if(nums[i]==nums[j]) { j++; } //找到和i不相等的元素就赋值给i下标的下一位内容 //就退出,i和j就继续比较 else { i++; nums[i]=nums[j]; break; } } } } return i+1; }
LeetCode链接:【88. 合并两个有序数组】
这种题型把两个数组和成升序,我们可以从后面开始排,数组1和数组2谁大,谁就放到后面,最后注意要判断数组2是否有元素剩下,如果有元素剩下要把剩下的元素拷贝到数组1中。
过程分析如下:
代码实现如下:
void merge(int* nums1, int nums1Size, int m, int* nums2, int nums2Size, int n){ //类似于归并排序,要从后面开始排 //从两个数组的最后一个元素开始比较 //大的就先往数组1后面放 int i=m-1; int j=n-1; int end=m+n-1; while(i>=0 && j>=0) { //比较数组末端的元素大小,大的往后面放 if(nums1[i]>nums2[j]) { nums1[end]=nums1[i]; i--; end--; } else { nums1[end]=nums2[j]; j--; end--; } } //排完后还有三种情况, //1.两个数组元素刚刚好放完 //2.把数组2的所以元素都放完了,还剩下数组1的一些元素 //3.把数组1的所有元素都放完了,还剩下数组2的一些元素 //这3种情况我们只需要处理第三种就可以了, //只有情况3没有把所有的元素都整合到数组1中。 if(j>=0) { while(j>=0) { nums1[end]=nums2[j]; j--; end--; } } }