当前位置：首页 > article >正文

初阶数据结构--顺序表

article 2025/3/25 21:07:46

第二讲顺序表

1. 线性表

在首先介绍顺序表之前需要先介绍一下线性表的相关知识。

线性表的概念：

线性表是n个具有相同特性的数据元素的有限序列（具有一类相同特性的数据结构的集合）。

常见的线性表：顺序表、链表、栈、队列、字符串……

在了解了什么是线性表之后，如何去描述一个线性表呢？这里从逻辑结构和物理结构的角度对线性表进行描述。线性结构一般指代认为想象出来的数据组成的形式，物理结构指代数据在内存上的存储形式。

线性表的描述：

线性表的逻辑结构：线性结构，也就是说其逻辑结构是一条直线。

线性表的物理结构：并不一定是连续的，线性表在物理上储存的时候，通常以数组和链式结构的形式存储。

2. 顺序表

在了解了线性表之后，顺序表作为线性表的一种也可以以相同的思想进行学习。

2.1 顺序表的概念和结构

2.1.1 概念

概念：顺序表是用一段物理地址连续的存储单元依次存储数据元素的线性结构，一般情况下采用数组的形式存储。

在这里插入图片描述

那么数组和顺序表的区别是什么呢？

顺序表的底层结构是数组，在数组的结构基础上对数组进行封装，实现了常用的增删改查等接口。

在这里插入图片描述

2.1.2 结构

顺序表由于其概念指出其物理地址是连续的，所以：

顺序表的逻辑结构：线性结构

顺序表的物理结构：线性结构

2.2 顺序表的分类

根据顺序表的定义可以知道顺序表本质就是对数组进行封装得到的一种数据结构，其底层结构还是数组。那么所谓的封装是什么呢？

这里的封装就是以结构体为基础，将数组名、有效数据个数、空间容量这些量统一封装在一个结构体中，组成的即为顺序表。

因为顺序表的底层是数组，如果是数组，在定义之前可能面对两种情况。

一种情况是定义之前已经知道数组大小，eg: int arr[3] = {1, 2, 3}
另一种情况即为定义之前还不知道数组大小，后续申请空间需要动态内存管理，eg: int* arr

2.2.1 静态顺序表

其中第一种情况的思想就是静态顺序表。静态顺序表是用固定的空间大小存储元素。

静态顺序表概念：使用定长数组存储元素。

静态顺序表的缺点：空间给小了不够用，给大了造成空间浪费。

2.2.2 动态顺序表

然后数组定义的第二种情况的思想就对应了动态顺序表。动态顺序表通过动态内存管理可以对储存数据的空间进行实时的扩容，使得整个数据不仅可以很好存储，还可以合理的实现内存的分配。

这就是顺序表的分类，经过介绍可以很清楚的知道动态顺序表的优越性，所以在下面实现顺序表的各种增删改查都会以动态顺序表为例子。

在文章的后面会通过SeqList.h、SeqList.c和test.c这三个工程文件，配合完成顺序表各种功能的实现。

SeqList.h：定义顺序表结构，声明要提供的操作
SeqList.c：具体实现各种操作
test.c：测试函数

2.3 动态顺序表的实现

2.3.1 构建动态顺序表

代码示例：

//SeqList.h

/*定义动态顺序表*/
typedef int SLDataType;

typedef struct SeqList
{
	SLDataType* arr;	//底层数组
	int size;			//有效数据个数
	int capacity;		//空间容量
}SL;

//typedef struct SeqList SL;

分析：

typedef int SLDataType;这句代码通过宏定义的方式，增大了代码后续的可维护性，如果后续放入顺序表的数据元素不是int类型而是char类型，只需要更改宏定义即可，不需要大费周章在工程中一个一个更改。
由于size 、capacity这两个参数都用于表述空间中的量，均为常数，所以不需要再使用宏定义对其数据类型进行更改。

2.3.2 动态顺序表的初始化

代码示例：

//SeqList.h

/*动态顺序表的初始化*/
void SLInit(SL* ps);

//SeqList.c

/*动态顺序表的初始化*/
void SLInit(SL* ps)
{
	ps->arr = NULL;
	ps->size = ps->capacity = 0;
}

分析：

（重点）这里的SLInit函数的参数是指向顺序表结构体的指针，而不是简单的将ps这个顺序表结构体当做参数传给SLInit函数。这里还是涉及了一个非常经典的传值调用和传址调佣的问题。
- 因为形参是实参的值的拷贝
- 传值：实参保存的值拷贝一份传给形参，实参和形参指向的是不同的地址，但是保存的数据都一样。
- 传址：形参指向的就是实参指向的地址。
- 在这个函数中，如果是传值调用，进入函数后，会对形参这个结构体中的arr初始化为NULL，再对形参中的size和capacity均初始化为0，但是因为形参和实参指向的并不是同一块地址，此时实参中的结构体还是处于未初始化的状态，如果后续调用这个未初始化的结构体SL可能会报错。

2.3.3 打印顺序表元素

所以为了更清楚的显示后续函数对于顺序表的操作效果，下面需要先写一个可以将顺序表中的元素都打印出来的函数，便于后续程序的调试。

代码示例：

//SeqList.h

/*打印顺序表中的元素*/
void SLPrint(SL* ps);

//SeqList.c

/*打印顺序表中的元素*/
void SLPrint(SL* ps)
{
	for (int i = 0; i < ps->size; i++)
	{
		printf("%d ", ps->arr[i]);
	}
	printf("\n");
}

就是简单的遍历结构体中的数组即可。

2.3.4 向顺序表中插入元素

一个线性排列的一行数据如果需要在其两端分别插入数据元素，需要分情况讨论也就是尾插和头插。

2.3.4.1 尾插

顾名思义，在顺序表的尾部插入数据元素就是尾插，但是在进行尾插时可能面临着此时尾部空间是否足够的问题，需要分情况讨论。

情况1：尾部空间充足

外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传

情况2：尾部空间不足

尾部空间不足，首先需要对空间进行扩容再对将数据元素插入到顺序表中。

问题1：然后如何增容是这里比较重要的问题。

在数据结构中顺序表的增容一般是成倍增加，eg：2→4→8→16→32······

**问题2：**那么为什么不可以一次增加一个呢？这样不就可以不产生空间的浪费了吗？

因为增容这一操作本身就有一定程序性能的消耗，如果频繁增容会导致程序效率低下。

**问题3：**增容会出现哪些问题？

连续空间足够，直接增容。
连续空间不够
- 重新找一块地址，分配足够的内存
- 拷贝数据到新的地址
- 销毁旧地址

代码示例：

//SeqList.h

/*检查顺序表空间是否充足,并实现增容*/
void SLCheckCapacity(SL* ps);

/*插入数据（尾差）*/
void SLPushBack(SL* ps, SLDataType x);

//SeqList.c

/*检查顺序表空间是否充足,并实现增容*/
void SLCheckCapacity(SL* ps)
{
	//判断空间是否充足
	if (ps->capacity = ps->size)
	{
		//增容 注意capacity为0的特殊情况
		int newCapacity = ps->capacity == 0 ? 4 : 2 * ps->capacity;
		
		SLDataType* tmp = realloc(ps->arr, newCapacity * sizeof(SLDataType));
		if (tmp = NULL)
		{
			perror("realloc fail!");
			exit(1);
		}
		ps->arr = tmp;
		ps->capacity = newCapacity;
	}
}

/*插入数据（尾差）*/
void SLPushBack(SL* ps, SLDataType x)
{
	//断言，防止传过来的顺序表指针为空指针
	assert(ps);

	/*方法2：
	if(ps == NULL)
	{
		return;
	}
	*/
	SLCheckCapacity(ps);
	ps->arr[ps->size++] = x;
}

分析：

SLCheckCapacity函数：因为后续的对顺序表进行插入数据的操作都需要确认现有的空间是否足够，所以可以把确认空间是否充足，并实现扩容这两个功能封装成一个函数SLCheckCapacity。在SLCheckCapacity函数中有以下问题：
- Capacity的增容：增容时2倍2倍的增容，但是 $0 * 2 = 0$ 是一个特殊情况，所以需要分类讨论。第8行int newCapacity = ps->capacity == 0 ? 4 : 2 * ps->capacity;通过一个三目操作符实现了检测顺序表此时的空间是不是0，如果是0则赋一个初值4，如果不是则将capacity增加到原来的两倍的功能。
- arr的增容：上面的第8行代码实现了对顺序表中变量capacity的扩容，但是数组arr中的空间还没有增容，下面通过动态内存管理函数realloc函数为数组arr申请了newCapacity个大小为SLDataType的空间。但是因为arr的后续空间有可能不够，无法开辟足够的空间。所以这里使用realloc函数，并将申请好的空间暂存在tmp中。
- 补充：最后将开辟好的（空间足够）的新的空间的地址传给arr，并改变Capacity的值为newCapacity。
SLPushBack函数：由于增容部分的功能函数SLCheckCapacity已经完成，SLPushBack函数SLPushBack函数只需要实现将新加入的数据x，放进顺序表中即可，并及时改变size的值。
- 补充：因为SLPushBack函数的参数会传进一个顺序表指针，因为后续将x插入进arr中，所以会对这个顺序表指针进行解引用，所以在解引用之前需要确认是不是空指针（NULL）。

**注意：**后续对顺序表的增删查改，都需要将顺序表指针传给对应函数，为了防止后续解引用报错，需要进行判断。

方式1：断言
```
assert(ps);
```
方式2：if判断，return退出
```
if(ps == NULL)
	{
		return;
	}
```

**时间复杂度：**O(1)

2.3.4.2 头插

头插就是在顺序表的头部插入数据，因为是插入数据，所以就需要考虑空间是否足够是否需要申请空间的问题。同时与尾插不同的是，头插因为是在头部插入，所以插入后的数据还需要在原来的基础上向后移动一位。

示例代码：

//SeqList.h

/*插入数据（头插）*/
void SLPushFront(SL* ps, SLDataType x);

//SeqList.c

/*插入数据（头插）*/
void SLPushFront(SL* ps, SLDataType x)
{
	//断言，防止传入的数据为空指针
	assert(ps);

	//判断空间是否足够
	SLCheckCapacity(ps);

	//数据整体后移一位，并空出下标为0的位置，插入数据x
	for (int i = 0; i < ps->size; i++)
	{
		ps->arr[i] = ps->arr[i + 1];
	}

	ps->arr[0] = 0;
	ps->size++;
}

分析：

因为后续需要对传入的顺序表指针进行解引用操作，所以先利用断言防止传入空指针。
使用前面定义的函数SLCheckCapacity判断空间是否足够。
利用for循环数据整体后移一位，并空出下标为0的位置，插入数据x即可实现头插，最后记得将size++；

**时间复杂度：**O(n)

2.3.5 删除顺序表中的元素

与向顺序表插入数据一样，删除顺序表中的数据也分为头删和尾删，需要分别编写对应函数实现功能。

2.3.5.1 尾删

要实现尾删只需要将size减1即可，不需要对最后一位数据做任何操作。

**注意：**顺序表为空的时候，不能删除

示例代码：

//SeqList.h

/*删除数据（尾删）*/
void SLPopBlack(SL* ps);

//SeqList.c

/*删除数据（尾删）*/
void SLPopBlack(SL* ps)
{
	assert(ps);
	assert(ps->size);

	ps->size--;
}

分析：

因为SLPopBlack函数中的参数为一个指向结构体的指针，为了保证后续解引用的正常编译，所以需要先对ps进行断言，防止传的为NULL。
为了保证顺序表不能跟为空，即结构体中的size的值不为0，所以对ps->size也进行断言处理。
最后在保证ps不是空指针和顺序表不为空的情况下，将size的值-1即可。

**时间复杂度：**O(1)

2.3.5.2 头删

对于顺序表的头删，可以采用和头插的逆向思路，在保证ps不是空指针和顺序表不为空的情况下，只需要将数组中的数据整体向前移动一位，在将size-1即可。

示例代码：

//SeqLise.h

/*删除数据（头删）*/
void SLPopFront(SL* ps);

//SeqLise.c

/*删除数据（头删）*/
void SLPopFront(SL* ps)
{
	assert(ps);
	assert(ps->size);

	for (int i = 1; i < ps->size - 1; i++)
	{
		//数组数据前移动
		ps->arr[i - 1] = ps->arr[i];
	}
	ps->size--;
}

分析：

首先还是通过两个断言，保证ps不是空指针和顺序表不为空的前提。
通过for循环，实现数据的整体前后移动，其中i的值的确定还是根据复杂度部分的思路**（等号右边都用 i 来表示下标，等号右侧根据实际情况+1或者-1）**

**时间复杂度：**O(n)

2.3.6 在指定位置插入数据

前文实现了在顺序表中的增加数据和删除数据，但是都是从顺序表的头部或者尾部增加或删除数据，下面将会介绍可以在顺序表中的任意指定位置插入数据。

示例代码：

//SeqList.h

/*指定位置插入数据*/
void SLInsert(SL* ps, SLDataType x, int pos);

//SeqList.c

/*指定位置插入数据*/
void SLInsert(SL* ps, SLDataType x, int pos)
{
	assert(ps);
	//指定位置不包含头部或者尾部
	assert(pos >= 0 && pos <= ps->size);

	//插入数据前先检测空间是否充足
	SLCheckCapacity(ps);

	//pos及其之后的数据整体后移一位
	for (int i = ps->size - 1; i < pos; i++)
	{
		ps->arr[i + 1] = ps->arr[i];
	}
	ps->arr[pos] = x;
	ps->size++;
}

分析：

SLInsert函数中的参数pos指的是想要插入在顺序表中的下标为pos的位置上。
这里的任意位置并不包括头部和尾部，因为前面已经实现的头插和尾插，对于这两种特殊情况，已经有了更加有针对性的的算法，所以这里的pos指向的是更加一般的位置。

2.3.7 在指定位置删除数据

示例代码：

//SeqList.h

/*在指定位置删除数据*/
void SLErase(SL* ps, int pos);

//SeqList.c

/*在指定位置删除数据*/
void SLErase(SL* ps, int pos)
{
	assert(ps);
	assert(ps->size);
	//指定位置不包含头部或者尾部
	assert(pos >= 0 && pos <= ps->size);

	//将pos后面的数据整体向前移动一位
	for (int i = pos + 1; i < ps->size - 1; i++)
	{
		ps->arr[i - 1] = ps->arr[i];
	}

	ps->size--;
}

分析：

首先作为删除功能要求保证传来的指针不为空和指针指向的顺序表中的数据不为空这就是前两句断言的含义，其次因为这里的指定位置同样不包含头部和尾部，原因同上。
这里的删除操作用数组前移，pos后面的数据整体前移一位即可覆盖掉pos即可实现删掉pos处的数据，最后不要忘记改变size的值。

2.3.8 在顺序表中查找数据

示例代码：

//SeqList.h

/*在顺序表中查找数据*/
int SLFind(SL* ps, int x);

//SeqList.c

/*在顺序表中查找数据*/
int SLFind(SL* ps, int x)
{
	assert(ps);
	for (int i = 0; i < ps->size; i++)
	{
		if (ps->arr[i] == x) 
		{
			//找到了，返回数据下标
			return i;
		}
	}
	//没有找到，返回一个无效下标
	return -1;
}

分析：

一个普通的数组遍历的思想即可解决，但是这个代码的逻辑仍然存在缺陷，因为在第一次找到这个数据就会返回，如果一个数据在这个顺序表中，多次重复出现这个函数只可以返回第一次出现的下标。

2.3.9 总结

上文对实现了动态顺序表的增删查改，通过上述函数的编写，可以在其中找到一些共性和规律。

断言部分
- **所以情况：**无论是实现如何功能的函数都需要接受传来的指向顺序表的指针，然而后续都需要对其进行解引用，所以首先要确保此指针不能是空指针。assert(ps);
- **删除数据：**因为对于一个空的没有数据的顺序表执行删除操作是没有意义的，所以也需要确保顺序表中的size的值不为0。assert(ps->size);
- **指定位置：**在对于在顺序表中的任意位置插入或删除数据的这种普适情况，pos指向的位置不应该包含头部和尾部。assert(pos >= 0 && pos <= ps->size);
特殊要求：
- **插入数据：**在顺序表中插入数据时，无论怎样插入都要求在插入之前判断空间是否充足，所以将判断空间是否充足和在空间不足的时候自动增容这两个要求封装成一个函数，每次插入数据的时候都事先调用即可。SLCheckCapacity(ps);
- 在顺序表除了尾部的任何地方处理数据：在实行头插、头删、在指定位置插入/删除数据以上四种情况都需要整体移动顺序表中的部分数据，在移动数据的时候需要利用for循环通过赋值语句实现前移或者后移，其中for循环中的各种参数的设定思路都参考第1讲复杂度 2.2.1 思路一中的补充介绍即可。

2. 算法实战

2.1 移除元素

题目链接：力扣-移除元素

题目描述：

给你一个数组 nums 和一个值 val，你需要原地移除所有数值等于 val 的元素。元素的顺序可能发生改变。然后返回 nums 中与 val 不同的元素的数量。

假设 nums 中不等于 val 的元素数量为 k，要通过此题，您需要执行以下操作：

更改 nums 数组，使前 k 个元素包含不等于 val 的元素。nums 的其他元素和 nums 的大小并不重要。
返回 k。

示例1：

输入：nums = [3 , 2 , 2 , 3]，val = 3

输出：2 , nums = [2 , 2 , _ , _ ]

解释：你的函数函数应该返回 k = 2，并且 nums 中的前两个元素均为 2。

你在返回的 k 个元素之外留下了什么并不重要（因此它们并不计入评测）。

示例2

输入：nums = [0 , 1 , 2 , 2 , 3 , 0 , 4 , 2]，val = 2

输出：5 , nums = [0 , 1 , 4 , 0 , 3 , _ , _ , _ ]

解释：你的函数应该返回 k = 5，并且 nums 中的前五个元素为 0 , 0 , 1 , 3 , 4。

注意这五个元素可以任意顺序返回。

你在返回的 k 个元素之外留下了什么并不重要（因此它们并不计入评测）。

提示：

0 <= nums.length <= 100
0 <= nums[i] <= 50
0 <= val <= 100

2.1.1 解法一

**思路：**定义两个变量指向数组第一个位置，判断nums[src]是否等于val

相等，src++
不相等，nums[dst] = nums[src]，src++，dst++

示例代码：

int removeElement(int* nums, int numsSize, int val) 
{
    int src = 0, dst = 0;
    while(src < numsSize)
    {
        //相等
        if(nums[src] == val)
        {
            src++;
        }
        //不相等
        else
        {
            nums[dst++] = nums[src++];
            //dst++;
            //src++;
        }
    }
    //此时dst的指就是保留下来与val不同的值
    return dst;
}

**时间复杂度：**O(n)

**空间复杂度：**O(1)

分析：

此思路运用两个下标变量，一个用于遍历数组与val比较，另一个用于保留下与val值不同的数据。
运用两个功能不同的下标变量作用于同一个数组，这样就不用再开辟一个新的数组空间用于一个个遍历再将数据一个个转存到新的数组空间中去。
这种思路在不能改变时间复杂度的前提下（因为需要遍历数组所以代码中的循环语句是无法省略的），不用开辟新的空间，降低了空间复杂度，实现了算法的优化。

2.1.1 解法二

**思路：**利用动态顺序表中的查函数，挨个查找，判断与val的值是否相等

相等，删除，后续数据前移
不相等，查下一个数据

2.2 删除有序数组中的重复项

题目链接：力扣-删除有序数组中的重复项

题目描述：

给你一个非严格递增排序的数组 nums，请你原地删除重复的元素，使每个元素只出现一次，返回删除后数组的新长度。元素的相对顺序应该保持一致。

考虑 nums 的唯一元素的数量为 k，你需要做以下事情确保你的题解可以被通过：

更改数组 nums，使 nums 的前 k 个元素包含唯一元素，并按照它们最初在 nums 中出现的顺序排列。nums 的其他元素与 nums 的大小不重要。
返回 k。

示例1：

输入：nums = [1 , 1 , 2]
输出：2 , nums = [1 , 2 , _]
解释：函数应该返回新的长度 2 ，并且原数组 nums 的前两个元素被修改为 1, 2 。不需要考虑数组中超出新长度后面的元素。

示例2：

输入：nums = [0 , 0 , 1 , 1 , 1 , 2 , 2 , 3 , 3 , 4]
输出：5 , nums = [0 , 1 , 2 , 3 , 4]
解释：函数应该返回新的长度 5 ，并且原数组 nums 的前两个元素被修改为 0, 1, 2, 3 ,4 。不需要考虑数组中超出新长度后面的元素。

提示：

1 <= nums.length <= 3 * 104
-104 <= nums[i] <= 104
nums 已按 非严格递增 排列

2.2.1 解法一

**思路：**定义两个指向数组下标的变量，dst指向第一个位置，src指向下一个位置，判断src和dst位置的数据

相等，src++
不相等，dst++，nums[dst] = nums[src]，src++

示例代码：

int removeDuplicates(int* nums, int numsSize) 
{
    int dst = 0, src = dst + 1;
    while(src < numsSize)
    {
        //相等，向后遍历
        if(nums[dst] == nums[src])
        {
            src++;
        }
        //不相等，将数据赋值给dst后面的一个数据
        else
        {
            nums[++dst] = nums[src++];
        }
    }
    //dst是下标从0开始，返回的是数组有效值数，需要+1
    return dst + 1;
}

分析：

通过两个下标变量，src用于遍历数组，dst用于重建新的顺序的数组。
重建的逻辑就在于**src因为是在dst后面一个，所以src只需要与dst比较，只要相同就不用管继续遍历，直到遇到第与dst不同的数，此时就是需要发生替换的情形，但是不可以直接替换dst，而是替换dst+1的值，因为此时dst和dst+1的值是相同的。**不断循环，直到新数组满足要求。
此时的代码并不是很完美，因为如果是一个完美的递增数组，每一个dst和src都不一样，每一次都需要进行替换，这显然十分多余。所以可以加上前提条件当dst与src在相邻位置时，此时尽管数据不同也不发生替换。

int removeDuplicates(int* nums, int numsSize) 
{
    int dst = 0, src = dst + 1;
    while(src < numsSize)
    {
        //条件判断
        if(nums[dst] == nums[src] && ++dst != src)
        {
            //因为是前置++，所以此时的dst已经完成了移位
            nums[dst] = nums[src];
        }
        src++;//继续遍历
    }
    //dst是下标从0开始，返回的是数组有效值数，需要+1
    return dst + 1;
}

2.3 合并两个有序数组

题目链接：力扣-合并两个有序数组

题目描述：

给你两个按 非递增顺序 排列的整数数组 nums1 和 nums2，另外有两个整数 m 和 n，分别表示 nums1 和 nums2 中的元素数目。

请你合并 nums2 到 nums1 中，使合并后的数组按 非递增顺序 排列。

注意: 最终，合并数组不应由函数返回，而是存储在数组 nums1 中。为了符合这种情况，nums1 的初始长度为 m + n，其中前 m 个元素表示已合并的元素，后 n 个元素为 0，应忽略。nums2 的长度为 n。

示例1：

输入：nums1 = [1 , 2 , 3 , 0 , 0 , 0], m = 3, nums2 = [2 , 5 , 6], n = 3
输出：[1 , 2 , 2 , 3 , 5 , 6]
解释：需要合并 [1 , 2 , 3] 和 [2 , 5 , 6] 。
合并结果是 [1 , 2 , 2 , 3 , 5 , 6] ，其中斜体加粗标注的为 nums1 中的元素。

示例2：

输入：nums1 = [1], m = 1, nums2 = [], n = 0
输出：[1]
解释：需要合并 [1] 和 [] 。
合并结果是 [1] 。

示例3：

输入：nums1 = [0], m = 0, nums2 = [1], n = 1
输出：[1]
解释：需要合并的数组是 [] 和 [1] 。
合并结果是 [1] 。
注意，因为 m = 0 ，所以 nums1 中没有元素。nums1 中仅存的 0 仅仅是为了确保合并结果可以顺利存放到 nums1 中。

提示：

nums1.length == m + n
nums2.length == n
0 <= m, n <= 200
1 <= m + n <= 200
-109 <= nums1[i], nums2[j] <= 109

2.3.1 解法一

思路：

创建3个下标变量，分别指向num1最后一个有效数据位（l1），num2最后一位有效数据位（l2）和num1空间中的最后一个位置（l3）。然后比较l1和l2数据的大小，谁大，谁向l3处存放数据，然后那个指针和l3均向前移动。

最后结束的条件：要么l1<0，要么l2<0

情况1：需要处理，需要将nums2中的数据，循环放进nums1中
情况2：不需要处理，因为nums2的数据已经有序放入nums1中了

示例代码：

void merge(int* nums1, int nums1Size, int m, int* nums2, int nums2Size, int n) 
{
    int l1 = m - 1;
    int l2 = n - 1;
    int l3 = m + n - 1;
    
    //l1 >= 0 l2 >= 0
    while(l1 >= 0 && l2 >= 0)
    {
        //nums1[l1]大
        if(nums1[l1] > nums2[l2])
        {
            nums1[l3--] = nums1[l1--];
        }
        else
        {
            //nums2[l2]大或者和nums1[l1]一样大
            nums1[l3--] = nums2[l2--];
        }
    }
    //跳出while循环有两种情况：要么l1<0（需要处理），要么l2<0（不需要处理）
    while(l2 >= 0)
    {
        nums1[l3--] = nums2[l2--];
    }
}

分析：

注意，第22行，在进行while循环条件的选取的时候，不可以写l1 < 0，因为int数据类型的限制，当l1等于0时候再-1之后并不会出现负数，而是一个极大的数，所以这里为了避免这种情况选择l2 >= 0即可。

查看全文

原文地址:https://blog.csdn.net/Tanecious/article/details/146409480
本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：http://www.kler.cn/a/596878.html 如若内容造成侵权/违法违规/事实不符，请联系邮箱：809451989@qq.com进行投诉反馈，一经查实，立即删除！