OJ题:移除元素、合并两个有序数组

简介: OJ题:移除元素、合并两个有序数组

1.原地移除元素


给你一个数组 nums 和一个值 val,你需要 原地 移除所有数值等于 val 的元素,并返回移除后数组的新长度。不要使用额外的数组空间,你必须仅使用 O(1) 额外空间并 原地 修改输入数组。元素的顺序可以改变。你不需要考虑数组中超出新长度后面的元素.


假设目前nums和val的值分别为:


e2.png


思路一:挨个遍历,当发现是val的时候,就把后面的元素挨个往前移动,覆盖val的值.


(但是思路一个时间复杂度为O(n^2))


e1.png


思路二:以空间换时间。首先我们把不是val的值放在动态开辟的数组空间中,然后把动态开辟的数组空间的值赋给nums,最后释放动态开辟的数组空间。(虽然题目明确要求不是使用额外的数组空间,但是我们还是得掌握这种方法哦)时间复杂度:O(n),空间复杂度O(n)



w4.png

思路三:双指针法,首先可以定义两个指针src和dst,如果src位置不是val就放到dst位置,然后src++,dst++。src位置是val,src++。时间复杂度:O(n),空间复杂度:O(1)


w3.png


通过以上三种算法的分析,我们可以发现思路三为最优算法


那我们就一起来实现思路三吧

w1.png



来来来,给各位武林侠士分析分析这个算法吧!!!


分析:首先把数组首元素地址、移除的值和元素的总共个数 传过去了,分别传给了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的值分别为:



q4.png

思路一:两个数组相比较,那个小就放在空数组中(虽然题目要求存储在nums1中,但是我们还是得了解这个思路)

q3.png



思路二:nums1和nums2都从后往前走,取大的从后往前放


q2.png


 通过以上二种算法的分析,我们可以发现思路二为最优算法


那我们就一起来实现思路二吧


q1.png


注:这个代码的实现就是思路二的算法,各位侠士们可以对着图看哦!!!


相关文章
|
存储
顺序表oj--移除元素&&删除重复项&&合并两个有序数组
顺序表oj--移除元素&&删除重复项&&合并两个有序数组
113 0
|
5月前
|
机器学习/深度学习 算法
【刷题记录】合并两个有序数组、移除元素
【刷题记录】合并两个有序数组、移除元素
|
8月前
27. 移除元素 88. 合并两个有序数组
27. 移除元素 88. 合并两个有序数组
41 0
|
8月前
|
存储
力扣 合并两个有序数列||移除元素
力扣 合并两个有序数列||移除元素
48 0
删除有序链表中重复的元素-II(链表)
双指针,slow和fast,并且增加标记flag初始为1。
61 0
链表OJ题目1 (移除链表元素)
力扣(链接放这里喽)
52 0
|
8月前
|
算法
算法题解-移除链表中的元素
算法题解-移除链表中的元素
移除元素、合并两个有序数组(leetcode)
移除元素、合并两个有序数组(leetcode)
|
算法 Go C++
【面试必刷TOP101】 删除有序链表中重复的元素-I & 删除有序链表中重复的元素-II
【面试必刷TOP101】 删除有序链表中重复的元素-I & 删除有序链表中重复的元素-II
55 0
|
C语言
单链表OJ题:LeetCode--203.移除链表元素
LeetCode.203:删除链表元素详细题解(带图)以及完整代码。
171 0
单链表OJ题:LeetCode--203.移除链表元素

热门文章

最新文章