前言
这篇文章,我们一起来看几道数组相关的面试题。
每道题目,我们给出的解题思路可能都不止一种,我们要不断分析讨论,找出最优的解题思路来实现。
一起来看看吧!!!
题目1:移除元素
题目链接放在这里,供大家练习:链接: link
先来看一下题目吧:
题目是什么意思呢?
其实就是给我们一个数组,还有一个值val,我们要删除这个数组中所有值和val相等的元素,然后返回删除之后的新数组的长度。
那怎么解决呢?接下来我们一起来分析一下:
思路1:暴力求解
思路1就是暴力求解,这也是我们可能最先会想到的一个方法:从头到尾找一个删除一个。
怎么做呢?
从数组的第一个元素开始,向后遍历,如何当前元素的值等于val的值,就删除。
怎么删呢?
将后面的元素,依次向前移动,将要删除的元素覆盖掉。后面也是如此,直至将数组中所有值等于val的元素都删除掉,就完成了。
那大家思考一下,这个方法好不好?
肯定是不太好的,如果给的数组中有大部分元素的值都等于val,比如像这样:
val的值是2,数组中所有等于2的元素,都要删除,每次删除都要挪动数据,等于val的元素越多,挪动的次数就越多,有些数据就会被不断地,重复的挪动,这样它的时间复杂度其实可以认为是O(N^2),效率就可能会比较低。
那这种方法我们就不实现了,我们再思考思考有没有更优的解法。
思路2:空间换时间
第一中解法暴力求解,它的时间复杂度太大了,那有没有更好的方法呢?
这里提供一种空间换时间的解法。
具体思路是这样的:
我们再额外创建一个数组,假设命名为tmp,然后对原数组进行遍历,如果当前元素不等于val,就把他拷贝到tmp数组中,如果等于val,不做处理,这样遍历结束,tmp数组中放的就是删除之后的元素,然后我们把tmp中的元素再拷贝回原数组,tmp的大小就是要返回的新长度。
那这种思路,它的**时间复杂度就是就是O(N)**了,与第一种方法的O(N^2)相比,就好很多了。
但它的的缺点在于:
我们又额外开辟了一个数组,该数组的大小与原数组等大,因此它的空间复杂度也是O(N)。这是他不好的地方。
而且呢,题目也要求:
所以,这还没有完,我们要继续优化,找出一个即效率高,还不用开辟额外空间的算法。
那有没有这样的解法呢?
当然有,其实我们对解法2再稍做优化,就行了。
思路3:双指针原地删除(解法2的再优化)
其实思路还是2的思路,只不过这次我们不再另外开辟一个新的数组了。
那要怎么搞呢?
思路分析
这里我们定义两个变量作为两个指针(注意这里说的指针只是一个形象化的称谓,不是用来存储地址的指针变量),开始它们都指向0下标的位置。
然后呢:
我们src指向的元素和val比较,如果不相等,就把src指向的元素赋值给dest指向的元素,即nums[dest]=nums[src],然后让dest和src都++。
然后再让src指向的元素和val比较,不相等继续上述操作,如果相等了,我们只让src++往后走,dest不动,然后再让src指向的元素和val比较,看是否等于val。
直至遍历完整个数组。
代码实现
那现在思路理清了,图也画出来了,接下来写代码就很简单了:
直接上代码:
int removeElement(int* nums, int numsSize, int val){ int src=0; int dest=0; while(src<numsSize) { if(nums[src]!=val) { nums[dest++]=nums[src++]; } else { src++; } } return dest; }
题目2:删除有序数组中的重复项
链接分享给大家:链接: link
一起看一下题:
这道题呢,其实就是让我们去重,数组中有些值重复出现,我们要让所有的元素都只出现一次,最终还是返回新数组长度。
这道题怎么做呢?
比较简单的一种方法还是利用双指针来解决。
思路:双指针
那这个题该如何利用双指针求解呢?
首先,还是定义两个变量作为指针,初始都指向下标为0位置。
如果两指针指向的元素相等,我们只让 src++往后走,过滤掉重复值。
如果不再相等,先让dest++,让后把src指向的元素赋值给dest指向的元素,然后再让src++。
然后再判断两指针指向的元素是否相等,重复上述操作,直至src遍历完数组。
最终dest+1就是去重后的数组长度。
代码实现
上代码:
int removeDuplicates(int* nums, int numsSize){ int src=0; int dest=0; while(src<numsSize) { if(nums[src]==nums[dest]) { src++; } else { // dest++; // nums[dest]=nums[src]; // src++; nums[++dest]=nums[src++]; } } return dest+1; }
题目3:合并两个有序数组
链接: link
常规合并方法
首先我们思考一下,如果给我们两个非递减的数组,我们如何去合并它们。
其实用双指针的方法还可以搞定,举个例子:
假如现在有这样两个数组:
如何合并?
两个指针分别指向两数组第一个元素,再开辟一个新数组,对他们进行比较,依次取较小的那个元素放到新数组中,如果相等,任选一个放入。
但是,对于这个题,这种方法可行吗?
显然是不可行的。
题目分析
为什么不可行呢?
我们来看这道题:
它给我们两个按 非递减顺序 排列的整数数组 nums1 和 nums2,确定是要求我们,但是要求我们把合并后的数组放到nums1 中。
也就是说,nums1 提前把空间开好了,已经足够放得下合并之后的整个数组了,不需要我们再额外开辟新数组了。
那上面那种方法显然就不适用了。
那这种情况我们应该怎么搞呢?
就拿题中这个例子来看:
如果我们还像上面那样从前往后两两比较大小,还可以吗?
如果nums2的的第一个元素就比nums1的小,那题目要求放到
nums1里,这样是不是就把nums2的第一个元素覆盖掉了啊。
所以这样搞不行。
那应该怎么办呢?
我们知道,nums1已经提前开好了多余的空间,这些空间在哪里啊,是在nums1有效数据的后面。
思路:三指针
所以我们怎么做比较好?
是不是从后往前倒着比较啊。
怎么比?
要取出两者中较大的元素放到后面,后面的数据我们覆盖掉是没问题的。
那接下来我来画图带大家再梳理一下思路:
这里需要我们再增加一个指针。
指针i1,i2分别指向数组nums1和nums2的最后一个元素,注意nums1是有效数据的最后一个,然后加一个dest指向nums1的最后一个位置。
然后开始比较:
i1,i2指向的元素哪个大,就把该元素赋值给dest指向的元素,然后dest和对应的i1或i2向前移动一个位置,继续比较。
相等的话,我们随便给哪一个都行
我这里就选择把i1指向的值给dest。
这一步的代码就是这样:
然后继续走:
走到这个位置我们发现
i2就走完了,遍历结束了,那此时是不是就完成了啊
这就是最终的状态了。
所以:
如果是i2先走完,i2走完就结束了,完成了。因为这些元素本来就在nums1中,不需要动了。
那也有可能是i1先走完啊,i1先走完是不是也直接结束了呢?我们来分析一下:
看这种情况:
还是按上面的方法依次进行比较。
但是这次我们会发现:
这次是i1先走完,但是这样结束了吗。
还没有,
我们需要把nums2中剩下的元素再拷贝到nums1前面的位置。
所以要注意:
如果是i1先走完,我们还需要继续处理,把nums2中剩余的元素放到nums1中。
代码实现
所以最终代码应该是这样的
void merge(int* nums1, int nums1Size, int m, int* nums2, int nums2Size, int n){ int i1=m-1; int i2=n-1; int dest=m+n-1; while(i1>=0&&i2>=0) { if(nums2[i2]>=nums1[i1]) { nums1[dest--]=nums2[i2--]; } else { nums1[dest--]=nums1[i1--]; } } while(i2>=0) { nums1[dest--]=nums2[i2--]; } }
再简单解释一下,相信大家就能很好的理解了:
首先说一下,题目里给的参数有些冗余
nums1Size和nums2Size其实不要也可以,因为nums1Size就是m+n,nums2Size就是n。
然后代码也简单提一下:
所以最终的代码就是这样。
好了,以上就是几个数组相关面试题的讲解,欢迎大家指正!!!