做题温馨提示
每个题的解题方法有很多,你不要纠结于它的优解, 先用最笨的方法(或者你能想到的方法解决出来), 然后自己在一步一步的优化。
移除元素
思路一:在nums数组中,一个元素一个元素的找,假设数组大小为N,如果第一个数等于val,那么就让第一个数 = 第二个数, 如果不想等,就跳过第一个数,比较第二个数 。
但是,时间复杂度通常考虑最坏的情况,
当数组中的元素,大部分或者基本都为val,那么就第一个数 = 第二个数(挪动n - 1次),第二个数 = 第三个数(挪动n - 2次)(这样遍历), …
时间复杂度(就为一个等差数列)
= n - 1 + n - 2 + n - 3 + … 1
= n^2 / 2 - n / 2
时间复杂度大O的渐进表示法:O(n^2)
空间复杂度 : O(n)
思路二:(以空间换时间, 创建一个数组)
第一步:创建一个数组tmp
第二步:用val,与nums数组中的元素挨个比较,如果数组中的元素 = val, 与下一个比较, 如果不相等, 把这个值 放到数组tmp中, 就这这样挨个遍历
第三步: 把tmp数组中的值,拷贝到nums数组中
时间复杂度(nums数组大小为 n, 比较了n次)
O(n)
空间复杂度:O(n)
时间复杂度 O(n)
思路三(优解):
有点类似于双指针思想
如图,
第一步,定义两个变量 int src = 0, dest =0 ;, 都代表着数组的下标
第二步:用nums[src]去与val比较,如果相同,src++,继续比较nums数组下一个元素,如果不相同, 那么让nums[dst] = nums[scr], 然后让src++, dst++,这样依次遍历
第三步:第二步完成之后, nums[dst] 就代表着移除之后的数组,可以让(dst = 0, dst = 1,…)挨个把移除后的数组打印出来, dst是数组下标, dst+1 便是这个数组的大小。
注意 scr++时候, scr大小不能够超过nums数组大小.
思路三最好自己画图理解一下
空间复杂度 O(1)
时间复杂度 O(n)
思路三的代码如下
int removeElement(int* nums, int numsSize, int val) { int scr = 0, dst = 0; while(scr < numsSize) { if(nums[scr] != val) { nums[dst] = nums[scr]; scr++; dst++; } else { scr++; } } return dst; }
删除有序数组的重复项
这道题就是个去重的问题,数据结构的题做的时候,一定要画图理解下
思路1与思路二,都跟上一题一样
这里我还是来介绍下,优解思路三
这里我定义数组的三个下标来做(2个下标也可以来做, )
如图
第一步:int i = 0, j = 1, dst = 0;
第二步:就让nums[i]与nums[j]进行比较, 如果相等, j++,如果不等,说明j,已经跳出了nums数组元素相等的那个区间了(因为题目说:这是一个有序的数组)
就让nums[dst] = nums[i], i = j, j++
注意:
可能会出现这样几种情况, j++就越界了,就结束了while(j < numsSize)这个循环
那么
第三步:单独对数组中最后一个元素进行处理, nums[dst] = nums[i];
第四步: return dst;
int removeDuplicates(int* nums, int numsSize) { if(numsSize == 0) //判断numsSize是否为0 { return 0; } int dst = 0, i = 0, j = 1; while(j < numsSize) { if(nums[i] == nums[j]) { ++j; } else { nums[dst] = nums[i]; dst++; i = j; j++; } } nums[dst] = nums[i]; dst++; return dst; }
:定义两个下标来做
原理是一样的,自己画图理解
代码如下;
int removeDuplicates(int* nums, int numsSize) { if(numsSize == 0) //判断numsSize是否为0 { return 0; } int i = 0, j = 1; while(j < numsSize) { if(nums[j] == nums[j - 1]) { j++; } else { nums[i] = nums[j - 1]; i++; j++; } } nums[i] = nums[j - 1]; i++; return i; }
合并两个有序的数组
[合并两个有序数组的链接](https://leetcode.cn/classic/problems/merge-sorted-array/description/)
思路一:跟前面思路二一样,用空间换时间,开辟一个新的数组。
思路二(优解):
思想:从数组最后一个元素比较,找最大的数(如果从数组第一个元素比较,找最小的数,那么将会出现问题,自己可以画图举例试试), 最大的数放在合并的数组下标那里,然后都下标都减减,就这样一次找,
下面看具体操作:
第一步:定义三个下标,int end1, end2, end; 分别为第一个数组的下标,第二个数组的下标,合并后数组的下标.
第二步:找最大数,如果num1[end1] < num2[end2]; 那么num1[end] = nums[end2], 然后end --, end2-- ,像这样比较,
要考虑两种情况,第一个数组(num1,为两个数组合并之后的数组)先结束的话,
如图, num1 [2, 2 ,3, 0, 0, 0] (这里面0,0,0 是合并后数组大小,并没有开始赋值,所以为0) num2[1, 1, 6]
2 > 1, end1–, 然后数组1先结束, 但是合并后的数组中, 并没有数组2中 (1, 1), 所以这里只需判断下, 把第二个数组剩余的值,赋给那个合并的数组哪里。
第二个数组先结束的话,
如图 结果就完成,剩下的 1,2,
无需变动,自然在数组num1中
思路二代码如下
void merge(int* nums1, int nums1Size, int m, int* nums2, int nums2Size, int n) { int end1 = m - 1, end2 = n - 1, end = m + n - 1; while(end1 >= 0 && end2 >= 0) { if(nums1[end1] > nums2[end2]) { nums1[end--] = nums1[end1--]; //这步意思是 //nums1[end] = nums1[end1]; // end--; //end1--; } else { nums1[end--] = nums2[end2--]; } } while(end2 >= 0) { nums1[end--] = nums2[end2--]; } }
轮转数组
消失的数字
这里两个题, 在我另一篇数据结构与算法的博客中有讲解,
博客链接如下:消失的数字,轮转数组的博客链接
当然你的关注与支持就是对我最大的鼓励,后面可能会有补充,敬请期待