1.原地移除元素
给你一个数组 nums 和一个值 val,你需要 原地 移除所有数值等于 val 的元素,并返回移除后数组的新长度。不要使用额外的数组空间,你必须仅使用 O(1) 额外空间并 原地 修改输入数组。元素的顺序可以改变。你不需要考虑数组中超出新长度后面的元素.
假设目前nums和val的值分别为:
思路一:挨个遍历,当发现是val的时候,就把后面的元素挨个往前移动,覆盖val的值.
(但是思路一个时间复杂度为O(n^2))
思路二:以空间换时间。首先我们把不是val的值放在动态开辟的数组空间中,然后把动态开辟的数组空间的值赋给nums,最后释放动态开辟的数组空间。(虽然题目明确要求不是使用额外的数组空间,但是我们还是得掌握这种方法哦)时间复杂度:O(n),空间复杂度O(n)
思路三:双指针法,首先可以定义两个指针src和dst,如果src位置不是val就放到dst位置,然后src++,dst++。src位置是val,src++。时间复杂度:O(n),空间复杂度:O(1)
通过以上三种算法的分析,我们可以发现思路三为最优算法
那我们就一起来实现思路三吧
来来来,给各位武林侠士分析分析这个算法吧!!!
分析:首先把数组首元素地址、移除的值和元素的总共个数 传过去了,分别传给了nums,val,sz在my_remove定义了两个整型变量src和dst,把这两个变量作为数组的下标去使用,运用循环去判断要是nums[src]不为val就把nums[src]的值赋值给nums[dst],否则nums[src]继续往后查找,直到不为val再赋值(注:把src和dst作为指针去查找也可实现,这个就交给各位侠士朋友了)
欧克欧克,那下面进入我们第二个OJ题吧!
2.合并两个有序数组
给你两个按 非递减顺序 排列的整数数组 nums1 和 nums2,另有两个整数 m 和 n ,分别表示 nums1 和 nums2 中的元素数目。
请你 合并 nums2 到 nums1 中,使合并后的数组同样按 非递减顺序 排列。
注意:最终,合并后数组不应由函数返回,而是存储在数组 nums1 中。为了应对这种情况,nums1 的初始长度为 m + n,其中前 m 个元素表示应合并的元素,后 n 个元素为 0 ,应忽略。nums2 的长度为 n 。
假设nums1和nums2,m和n的值分别为:
思路一:两个数组相比较,那个小就放在空数组中(虽然题目要求存储在nums1中,但是我们还是得了解这个思路)
思路二:nums1和nums2都从后往前走,取大的从后往前放
通过以上二种算法的分析,我们可以发现思路二为最优算法
那我们就一起来实现思路二吧
注:这个代码的实现就是思路二的算法,各位侠士们可以对着图看哦!!!