【刷题篇】顺序表

Bertha 。 2024-03-27 13:36 82阅读 0赞

### ![391abd54cb80452f959d2fef66a0b886.gif][] ###

### 1.前言 ###

在之前，我们学习了顺序表的概念与实现，其基本概念如下：

> **顺序表**是用一段物理地址连续的存储单元依次存储数据元素的线性结构，是线性表中的一种，分为静态顺序表和动态顺序表。一般情况下采用数组存储，支持元素的随机访问。在数组上完成数据的增删查改。

而本期，我们将通过两道在线OJ题来巩固顺序表的基础知识，这两道题分别来自LeetCode 27移除元素和LeetCode 88合并两个有序数组。

### 2.[移除元素][Link 1] ###

#### 1.题目 ####

![bdf47678b00a492abb07c345aececf78.png][]

--------------------

#### 2.初步分析 ####

第一眼我们的想法可能是再开辟一个新数组，然后遍历原数组，把不等于val的数值放入新数组中即可完成移除。过程如下：

![f64207e1756442158e3129ae100c286f.gif][]

> 但是这样的空间复杂度为O(N)，不符合题目的要求，题目要求我们原地移除元素。

**我的思路是**：将数组中不等于val的值移到数组前面。定义两个变量left和right用来表示数组的下标，right向后遍历数组，当nums\[right\]不为val时，则将nums\[right\]赋值给nums\[left\]，然后left++、right++，否则right++，循环直到right等于数组长度。其空间复杂度为O(1)。动图过程如下：

![1f486f97e5fe4ade9146dd84b1902309.gif][]

> 我们发现，最后left前的元素即为我们需要的数组元素，且left即为移除后元素个数

#### 3.代码实现 ####

//接口型OJ
    int removeElement(int* nums, int numsSize, int val)
    {
    	int right = 0;
    	int left = 0;
    	for (right = 0; right < numsSize; right++) //右指针遍历一遍数组
    	{
    		if (nums[right] != val)  //不为val就往前放
    		{
    			nums[left] = nums[right];
    			left++; //左指针右移
    		}
    	}
    	return left; //left即为移除后所需元素个数
    
    }

### 3[合并两个有序数组][Link 2] ###

#### 1.题目 ####

![21d8dc08efc843bc86b8dfaef4a200fa.png][]

#### 2.初步分析 ####

本题的目的是将两个有序数组从小到大归并到一个数组中。我们依旧可以遍历两个数组的元素进行对比，将满足条件的元素放入归并后数组中。但是由于题目要求将nums1和nums2数组归并到nums1中，所以我们不能从左往右遍历两个数组，将小的放入nums1中，否则会出现以下情况：

![9dc637e1d0304269884950696a4aff8c.gif][]

> 显然，这样做显然会造成nums1的数据丢失，导致出错。

**我的思路是**：我们可以发现，由于nums1的数组空间是m+n，所以后面n个空间是空的。我们可以利用这个特点，从右往左反向遍历数组，将元素进行比较，较大者放于数组后面，从后往前放，如下：

![3875c2eabae7414d8f69b1207eb4c45b.gif][]

--------------------

> **这个算法需要注意的是**：循环的结束条件是end1和end2其中一个小于0 ，当end2先小于零时，说明我们已经按照顺序将num2数组的元素全部归入num1了，就无需再做处理。但当num1先小于零时，此时nums2数组的数据并未全部归并到nums1中，我们还需将nums2剩余元素放入nums1中。此算法的时间复杂度为O(M+N)。

#### 3.AC代码实现 ####

//接口型OJ
    void merge(int* nums1, int nums1Size, int m, int* nums2, int nums2Size, int n) 
    {
    	int end1 = m - 1;
    	int end2 = n - 1;
    	int end = nums1Size - 1;
    	while (end1 >= 0 && end2 >= 0) //双指针，从后往前找最大元素
    	{
            //将最大元素放入nums1数组后面
    		if (nums1[end1] > nums2[end2])
    		{
    			nums1[end] = nums1[end1]; 
    			end1--;
    			end--;
    		}
    		else
    		{
    			nums1[end] = nums2[end2];
    			end2--;
    			end--;
    		}
    	}
    	while (end2 >= 0) //如果nums1先遍历结束，需要将nums2剩余数据放入nums1
    	{
    		nums1[end] = nums2[end2];
    		end2--;
    		end--;
    	}
    
    }

--------------------

***以上，就是顺序表刷题的全部内容。***

***制作不易，能否点个赞再走呢qwq***

[391abd54cb80452f959d2fef66a0b886.gif]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/27/5ee5bcf1d7ba4e5ba3a63eb86b86e809.png
[Link 1]: https://leetcode.cn/problems/remove-element/
[bdf47678b00a492abb07c345aececf78.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/27/846a47139ce24b6388aa086c82809964.png
[f64207e1756442158e3129ae100c286f.gif]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/27/8ab51907aaf54d5baf468daf1e7745d4.png
[1f486f97e5fe4ade9146dd84b1902309.gif]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/27/4f702a8d07b744b1bd9320ad767fcabb.png
[Link 2]: https://leetcode.cn/problems/merge-sorted-array/
[21d8dc08efc843bc86b8dfaef4a200fa.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/27/e67a44ace3964a4297aafa0cfbf5bb12.png
[9dc637e1d0304269884950696a4aff8c.gif]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/27/6fba9ab53555431cbd9b3a0dedf3b61c.png
[3875c2eabae7414d8f69b1207eb4c45b.gif]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/27/0dbfc8411cf543f4b34ce864a1cd0c5e.png

发表评论取消回复

表情：

评论列表（有 0 条评论，82人围观）

还没有评论，来说两句吧...

相关阅读

相关【刷题篇】链表（下）

?各位读者们好，本期我们来填填之前留下的坑，继续来讲解几道和链表相关的OJ题。但和上期单向链表不一样的是，我们今天的题目主要是于环形链表有关，下面让我们一起看看吧。?环形...

╰半夏微凉°/ 2024年04月25日 20:03/ 0 赞/ 84 阅读

相关【刷题篇】链表（上）

?前段时间我们学习了单向链表和双向链表，本期将带来3道与链表相关的OJ题来巩固对链表的理解。话不多说，让我们进入今天的题目吧！?反转单链表链表的中间结点合并两个有序链表反...

快来打我*/ 2024年04月25日 20:02/ 0 赞/ 90 阅读

相关【刷题篇】顺序表

![391abd54cb80452f959d2fef66a0b886.gif][] 1.前言在之前，我们学习了顺序表的概念与实现，其基本概念如下： > 顺序表是

Bertha 。/ 2024年03月27日 13:36/ 0 赞/ 83 阅读

相关 leetcode的刷题顺序

LeetCode上的题目种类繁多，根据个人的编程经验和目标，选择刷题的顺序可以有所不同。以下是一些建议的LeetCode刷题顺序：数据结构和基础算法：从数据结构入手，先

曾经终败给现在/ 2024年03月24日 20:29/ 0 赞/ 81 阅读

相关 ACM刷题之路（十二）数据结构——顺序表

这周已经是第九周了，为了期末的时候能够兼顾其他课程的复习，所以提早对数据结构这门课进行回顾总结。数据结构忽略前面两章的C语言基础(有机会以后再补)，直接从第三章最简单的线性

青旅半醒/ 2023年10月21日 07:28/ 0 赞/ 93 阅读

相关 MySQL刷题篇(一）

![在这里插入图片描述][b58e14a606c14e76832adc977e9ba0ba.gif_pic_center] 文章目录一、查询所有列二、查

分手后的思念是犯贱/ 2023年09月27日 12:31/ 0 赞/ 98 阅读

相关力扣刷题：链表篇

目录 1290. 二进制链表转整数题目介绍题目实现 138. 复制带随机指针的链表题目介绍

￡神魔★判官ぃ/ 2022年10月16日 09:40/ 0 赞/ 269 阅读

相关线性表之顺序表刷题

线性表之顺序表刷题 1. 从顺序表中删除具有最小值的元素（假设为一）并由函数返回被删除元素的值。空出的位置由最后一个元素填补，若顺序表为空则显示出错信息并退出运行。

￡神魔★判官ぃ/ 2022年10月12日 05:56/ 0 赞/ 149 阅读

相关剑指offer刷题总结——链表篇（二）

1.链表中环的入口结点【题目】链表中环的入口结点给一个链表，若其中包含环，请找出该链表的环的入口结点，否则，输出 null。【代码】 package

Dear 丶/ 2021年09月21日 04:48/ 0 赞/ 337 阅读

相关剑指offer刷题总结——链表篇（一）

1.从尾到头打印链表【题目】输入一个链表，按链表从尾到头的顺序返回一个 ArrayList。【代码】 package swear2offer.link

痛定思痛。/ 2021年09月21日 03:14/ 0 赞/ 343 阅读