1、移除元素
1.1、题目描述
1.2、思路讲解
思路一:(时间复杂度O(N^2)
如果数组元素等于val,则将后面的元素往前挪动一个位置。
思路二:(空间复杂度O(N)不符合题目要求)
用空间换时间,将不等于val的值赋值到新的数组,然后将新的数组赋值给原数组。
思路三:(时间复杂度O(N))
用双指针,一个指针(src)用来遍历数组,一个指针(dest)用来遍历有效数据,遍历一遍数组,如果该值等于val,那么src++,如果该值不等于val,将src位置的元素赋值到dest位置,然后src++,dest++,因为dest是后置++,先使用再+1,因此dest就是有效数据个数。
1.3、画图分析
下图为思路三的画图分析喔,想了解其他思路的分析私信博主喔!
1.4、代码实现
思路三
int removeElement(int* nums, int numsSize, int val) { int dest=0; int src=0; while(src<numsSize) { if(nums[src]!=val) { nums[dest++]=nums[src++]; } else { src++; } } return dest; }
此处只需返回不等于val值的个数,因此可以少去等于val的判断,代码实现如下。
int removeElement(int* nums, int numsSize, int val) { int i=0; int count=0; for(i=0;i<numsSize;i++) { if(nums[i]!=val) { nums[count]=nums[i]; count++; } } return count; }
2、删除有序数组
2.1、题目描述
2.2、思路讲解
思路一:(时间复杂度O(N^2)空间复杂度O(1))
遍历数组,如果前面一个数等于后面一个数,将后面的所有元素向前移动一个位置。但是最后一个需要特殊处理,因为最后一个位置没有元素与之相比,处理的方式就是直接将最后一个数据放入有序数组的最后一个即可。
思路二:(时间复杂度O(N)空间复杂度O(N))
用空间换时间,将前后的数据进行比较,前后不相等则放入新数组中,同样需要处理最后一个数据,处理的方式是直接将最后一个数据放入有序数组的最后一个即可。
思路三:(时间复杂度O(N)空间复杂度O(1))
使用双指针,一个指针(src)用来遍历数组,一个指针(dest)用来记录有效数据,如果前后不相等则将元素放入下标dest中,然后src++,dest++,如果相等则src++。
2.3、画图分析
思路三
2.4、代码实现
思路一
int removeDuplicates(int* nums, int numsSize) { for(int i=0;i<numsSize;i++) { for(int j=i+1;j<numsSize;j++) { if(nums[i]==nums[j]) { for(int k=j;k<numsSize-1;k++) { nums[k]=nums[k+1]; } j--; numsSize--; } } } return numsSize; }
思路三
int removeDuplicates(int* nums, int numsSize) { int dest=0; int src=0; while(src<numsSize-1) { if(nums[src]!=nums[src+1]) { nums[dest]=nums[src]; dest++; src++; } else { src++; } } nums[dest++]=nums[src];//最后一个元素的处理 return dest; }
3、合并两个有序数组
3.1、题目描述
3.2、思路讲解
思路一:(时间复杂度O(m+n)空间复杂度O(m+n)
开辟一个新的数组,大小为m+n(使用变长数组),比较两个数组的数值,哪个小则依次放入新的数组中,最后把新的数组的值赋值到nums1中。
C99标准中,新增了可变长度数组。在leetcode,牛客等刷题网站可以使用变长数组,但是VS不支持。
变长数组中的“变”不是指可以修改已创建数组的大小,一旦创建了变长数组,它的大小则保持不变。这里的“变”指的是:在创建数组时,可以使用变量指定数组的长度。(普通数组只能用常量或常量表达式指定数组的长度)
思路二:
从两个数组的末尾比较数值,大的值放入nums1的最后一个,依次类推,(前提是有序数组)。需要注意nums2是否赋值完,nums2赋值完不需要加判断,没有赋值完则需要加判断。
3.3、画图分析
思路二
3.4、代码实现
思路二
void merge(int* nums1, int nums1Size, int m, int* nums2, int nums2Size, int n) { int end1 = m-1; int end2 = n-1; int end = m + n - 1; while (end1 >= 0 && end2 >= 0) { if (nums1[end1] > nums2[end2]) { nums1[end] = nums1[end1]; end--; end1--; } else { nums1[end] = nums2[end2]; end--; end2--; } } while (end2 >= 0)//nums2还剩数值 { nums1[end] = nums2[end2]; end--; end2--; } }
总结
本篇博客就结束啦,谢谢大家的观看,如果公主少年们有好的建议可以留言喔,谢谢大家啦!