扬帆数据结构算法之舟，启航C++探索征途——LeetCode深度磨砺：顺序表技术精进实践

人无完人，持之以恒，方能见真我！！！
共同进步！！

顺序表练习

知识就是拿来用的，我们前面刚刚学习了顺序表，我们这就来学习使用它

那么是不是就说明我们以后要用数据结构做题就必须把它手写一遍吗？这是不需要的，后面我们会介绍C++，在C++中的STL中有现成的可以用，现在在我们的初阶数据结构的学习过程中，就复制我们写过的数据结构来做题

在做题过程中，我也会穿插时间复杂度和空间复杂度的介绍，也是对之前内容的一个复习

1.移除数组中指定的元素

题目链接：移除元素

方法1（顺序表）

根据图片我们可以了解题意，就是让我们删除nums数组中和val相等的值，然后返回删除后的数组的有效元素个数

方法1的思路就是直接使用我们前面写的顺序表，在顺序表中我们写了一个查找函数和一个删除指定位置元素的函数，将这两个函数结合就可以在顺序表中查找指定的要删除的元素的下标，然后返回给删除函数

我们要做这道题的第一步就是先把我们前面写的顺序表拷贝过来，但是你要是有时间的话也可以手写一遍，复习一遍加深记忆，在使用顺序表之前，我们可以先把初始化函数和销毁函数协商，避免忘记销毁顺序表

随后把数组中的内容尾插到我们的顺序表，我们才能使用顺序表对数据进行操作，如下：

int removeElement(int* nums, int numsSize, int val) 
{
    int i = 0;
    SL sl;
    SLInit(&sl);
    for(i = 0; i<numsSize; i++)
    {
        SLPushBack(&sl,nums[i]);
    }

    SLDestroy(&sl);
}

随后我们就可以根据我们写的查找函数SLFind 来设计一个循环，让它能够遍历数组的元素，然后每找到一个指定的val元素，就使用删除函数删除，这个循环的结束条件就是，SLFind返回-1，如果返回的不是-1，就继续查找

首先如果没有元素那么久不进入循环，如果不是就进入循环将对应的元素删除，是的话就结束循环，如下：

	while(!SLEmpty(&sl) && SLFind(&sl,val) != -1)
    {
        int ret = SLFind(&sl,val);
        SLErase(&sl,ret);
    }

typedef int type;

typedef struct SL
{
	type* arr;
	int size;
	int capacity;
}SL;


void SLInit(SL* ps);
void SLDestroy(SL* ps);

void SLPushBack(SL* ps, type x);

void SLPrint(SL* ps);

void SLPushFront(SL* ps, type x);

void SLPopBack(SL* ps);

void SLPopFront(SL* ps);

void SLInsert(SL* ps, int pos, type x);

int SLFind(SL* ps, type x);

void SLErase(SL* ps, int pos);


void SLInit(SL* ps)
{
	ps->arr = NULL;
	ps->size = ps->capacity = 0;
}

//销毁
void SLDestroy(SL* ps)
{
	if (ps->arr)
		free(ps->arr);
	ps->arr = NULL;
	ps->size = ps->capacity = 0;
}

//如果空间不够，进行扩容
void SLcheckCapacity(SL* ps)
{
	if (ps->capacity == ps->size)
	{
		ps->capacity = ps->capacity == 0 ? 4 : ps->capacity * 2;
		type* tmp = (type*)realloc(ps->arr, ps->capacity * sizeof(type));
		if (tmp == NULL)
		{
			perror("realloc");
			exit(1);
		}
		ps->arr = tmp;
		tmp = NULL;
	}
}

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

//尾插
void SLPushBack(SL* ps, type x)
{
	assert(ps);
	SLcheckCapacity(ps);
	ps->arr[ps->size++] = x;
}

//头插
void SLPushFront(SL* ps,type x)
{
	assert(ps);
	SLcheckCapacity(ps);
	memcpy(ps->arr + 1, ps->arr, ps->size * sizeof(type));
	ps->arr[0] = x;
	ps->size++;
}

//尾删
void SLPopBack(SL* ps)
{
	assert(ps);
	assert(ps->size);
	ps->size--;
}

//头删
void SLPopFront(SL* ps)
{
	assert(ps);
	assert(ps->size);
	memmove(ps->arr, ps->arr + 1, --ps->size * sizeof(type));
}

//指定位置前插入数据
void SLInsert(SL* ps, int pos, type x)
{
	assert(ps);
	assert(pos >=0 && pos <= ps->size);
	memmove(ps->arr + pos + 1, ps->arr + pos, (ps->size - pos) * sizeof(type));
	ps->arr[pos] = x;
	ps->size++;
}

int SLFind(SL* ps, type x)
{
	assert(ps);
	assert(ps->size);
	for (int i = 0; i < ps->size; i++)
	{
		if (ps->arr[i] == x)
			return i;
	}
	return -1;
}

//删除指定位置的数据
void SLErase(SL* ps, int pos)
{
	assert(ps);
	assert(ps->size);
	assert(pos >= 0 && pos <= ps->size);
	memmove(ps->arr + pos, ps->arr + pos + 1, (ps->size - pos - 1) * sizeof(type));
	ps->size--;
}

bool SLEmpty(SL*ps)
{
    return ps->size == 0;
}

int removeElement(int* nums, int numsSize, int val) 
{
    //如果为空就返回0
    if(numsSize == 0) return 0;
 
    //初始化
    SL sl;
    SLInit(&sl);
    //将元素放入顺序表
    int i = 0;
    for( i = 0;i < numsSize;i++)
    {
        SLPushBack(&sl,nums[i]);
    }

    //查找元素+删除元素
    while(!SLEmpty(&sl) && SLFind(&sl,val) != -1)
    {
        int ret = SLFind(&sl,val);
        SLErase(&sl,ret);
    }
    //将删除后的元素放回nums数组
    for(i = 0;i<sl.size;i++)
    {
        nums[i] = sl.arr[i];
    }
    
    //保存元素个数,销毁函数后，并返回
    int k = sl.size;
    SLDestroy(&sl);
    return k;
}

可以看到我们Ctrl + c v 在加上写的代码已经达到了一百六十行，这样写不仅繁琐，而且拷贝的时候还容易出错

可以看到最后通过了，我们来分析一下代码的时间复杂度和空间复杂度，第一个和第二个for循环都是O(N)，关键在于第二个while循环的时间复杂度

由于我们的查找方法和删除方法时间复杂度都是O(N)，外层有一个while循环，所以时间复杂度就是O(N^2)

接着来看空间复杂度，我们为了在顺序表中操作数组的数据，所以把数组中的数组全部放入了顺序表，所以顺序表会额外开辟数组元素大小的空间，空间复杂度为O(N)

我们知道这个时间复杂度和空间复杂度都不是很好，所以我们还有另外一种优化的方法

方法2（双指针）

这里的双指针并不是创建两个指针变量，而是数组中的下标，因为数组中我们能够通过下标来访问元素，与指针相似，所以叫做双指针

具体方法就是创建两个整型变量src和dest，，src代表源，dest代表目的地

在双指针算法中，我们的思路很简单，就是首先让src和dest都指向数组的第一个元素，随后我们就看src位置上的值是否是题目给出的val，如果是我们就直接让src往后走一步

如果不是，我们就把src位置上的值赋给dest，随后让dest和src都往后走一步，接下来我们就演示一下第一个示例的推演，如图：

有了上面的分析，我们就可以有一些思路了，首先创建两个整型变量src和dest作为我们的双指针，初始情况下让它们都为0

随后创建一个循环，循环条件就是src < numsSize，因为src是数组中的下标，要保证它不能越界，接着我们就进行判断，如果src位置的值等于dest位置的值，那么直接让src++

否则的话就是不等于，那么把src位置的值赋值到dest位置，随后让它们都++，如下：

int removeElement(int* nums, int numsSize, int val) 
{
    //循环条件 src < numsSize
    int src = 0,dest = 0;
    while(src < numsSize)
    {
        if(nums[src] == val)
        {
            src++;
        }
        else
        {
            nums[dest++] = nums[src++];
        }
    }
    //循环结束，dest 就是指向最后一个元素的后一个，就是元素个数
    return dest;
}

最后我们提交一下就通过了，在双指针方法中，我们只有一个循环，时间复杂度为O(N)，申请的空间也是常数个，所以时间复杂度为O(1)，可以看到比使用顺序表的方法简便多了，时间复杂度和空间复杂度都优化了一个档次

这道题的双指针法的本质就是 探路法 ，碰到了指定的元素就不管，直接跳过，然后把不是指定的元素放在前面，简单地说就是一个在前面探路，一个在后面接收

2.删除有序数组中的重复项

题目链接：删除有序数组的重复项

方法1（顺序表）

既然我们的标题是顺序表练习，那我们第一种方法还是用顺序表来做

根据上面图片的解释，我们大致明白了题目的要求，就是数组是相对有序的，然后我们要删除那些重复项，让数组里面的元素变得唯一且有序，最后返回唯一的元素个数，至于其它位置的元素就不管了

首先还是把顺序表拷贝过来，以及初始化，销毁，这些都不要忘记，然后把数组数据尾插到顺序表中上面讲过了，接着我们就来讲这道题不同的地方

由于数组是相对有序的，所以相同的元素肯定是放在一起的，所以我们就可以写一个循环来判断前后两个元素是否相等，如果相等我们就删除当前的元素，每删除一个元素numsSize就减1，要特别注意的一个点是要保证下标的有效性，如下：

for (i = 0; i < numsSize; i++)
{
    if (i + 1 < numsSize && sl.arr[i] == sl.arr[i + 1])
    {
        SLErase(&sl, i);
        numsSize--;
    }
}

但是我们的代码通过不了这个测试用例

来调试一下看看问题出在哪里

这个时候我们发现了问题，当i = 1时，将下标为1的元素删除了，所有后面的其它元素都往前挪动了一步，导致现在下标为1和2的元素又相等了

但是本次循环结束了，下一次在循环中i要++变成了2，i+1变成了3，比较不了下标为1和2的元素了，也就导致了下标为1和2的元素相等没有处理，如果看不懂这里的分析也没有关系，自行调试一下就明白了

那么怎么解决呢？其实也很简单，问题就出在删除一个相同元素后，其余元素都往前挪动了，但是循环结束了，i要++，就不会再比较移动后的i下标位置的元素和i+1下标的元素了

所以我们为了能够让它删除元素后，多比较一次原本移动后的i下标位置的元素和i+1下标的元素，我们可以在删除一个元素后让i- -，这样处理后下次进入循环i的值就不会变化，代码如下：

for (i = 0; i < numsSize; i++)
{
    if (i + 1 < numsSize && sl.arr[i] == sl.arr[i + 1])
    {
        SLErase(&sl, i);
        numsSize--;
        i--;
    }
}

当完成上面的步骤之后我们再把顺序表中的数据拷贝回原数组中，此时的numsSize就是有效的元素个数

int removeDuplicates(int* nums, int numsSize)
{
    SL sl;
    int i = 0;
    SLInit(&sl);
    for (i = 0; i < numsSize; i++)
    {
        SLPushBack(&sl, nums[i]);
    }
    for (i = 0; i < numsSize; i++)
    {
        if (i + 1 < numsSize && sl.arr[i] == sl.arr[i + 1])
        {
            SLErase(&sl, i);
            numsSize--;
            i--;
        }
    }
    for (i = 0; i < numsSize; i++)
    {
        nums[i] = sl.arr[i];
    }
    SLDestroy(&sl);
    return numsSize;
}

最后我们提交一下就可以通过了，在这个方法中，我们的时间复杂度也是很高的，达到了O(N^2)，并且由于使用顺序表拷贝了原数组中的内容，空间复杂度也不低，达到了O(N)，所以我们接下来介绍一个更好的方法

方法2（双指针）

这道题还是可以使用我们的双指针法来做，上一题的本质就是探路法

这道题也可以借鉴这样的思想，我们题目要求去掉相对有序的数组中的元素，说明相等的元素都是挨在一起的，我们还是可以定义两个变量src和dest，src在前面探路，dest在后面接收

具体思路就是：初始情况下让dest指向第一个元素，而src指向第二个元素，因为如果它们都指向第一个元素，那么它们肯定就相等了，没有比较的必要，所以让src走到第二个元素的位置上

然后我们就比较src和dest位置上的元素是否相等，如果相等我们就让让src++，其它什么都不做，如果不相等就让dest++，然后把src位置的值赋值到dest位置上，然后再让src++，听着可能有点懵，我们来画个图理解一下，就知道这个思路了

具体的例子我们就参考题目给出的第一个示例，如下：

有了上图的解析，我们现在就可以直接来写代码了，首先创建一个while循环，
循环条件就是src < numsSize

然后如果src指向的元素等于dest指向的元素，就让src++，其它什么都不做，如果不相等，就让dest先++，再把src位置的元素赋值给dest位置的元素，最后让src++，如下：

while (src < numsSize)
{
    if (nums[src] == nums[dest])
    {
        src++;
    }
    else
    {
        dest++;
        nums[dest] = nums[src];
        src++;
    }
}

最后循环结束返回 dest + 1

int removeDuplicates(int* nums, int numsSize) 
{
    int src = 0, dest = 0;
    while(src < numsSize)
    {
       if(nums[src] == nums[dest])
          src++;
       else
          nums[++dest] = nums[src++];
    }
    return dest+1;    
}

最后也是成功提交了代码，我们来分析一下双指针法的时间复杂度和空间复杂度，我们只用了一个循环，时间复杂度为O(N)，也没有额外申请空间，所以空间复杂度为O(1)

3.双指针练习之合并两个有序数组

题目链接:合并两个有序数组

方法1（直接排序）

先来解读一下题目，题目给了我们两个数组，其中第一个nums1 的大小是两个数组的和（m+n）,因为我们要将nums2合并到nums1中去，要保证空间足够，所以题目才给出这样的条件

首先题目告诉我们两个数组都是非递减的数组，所以有两种可能，一是递增，二就是可能是重复数据
,现在题目要求我们将他俩合并成有序数组返回

第一个和方法就是，直接将nums2拷贝到nums1中，再对nums1进行排序，我们可以使用qsort函数实现排序

代码的实现过程就不再多讲了，思路很简单，这里我们直接给出完整代码：

#include <stdlib.h>
//这个函数的意思就是比较数组中的元素大小
int int_compare(const void* e1,const void* e2)
{
    return *(int*)e1 - *(int*)e2;//前-后<0就是升序
}

void merge(int* nums1, int nums1Size, int m, int* nums2, int nums2Size, int n) 
{
    //将nums2放进nums1，所以循环条件应该小于n
    for(int i = 0;i<n;i++)
    {
        nums1[i + m] = nums2[i];//这里是将nums2放在nums1的m位置之后
    }
    qsort(nums1,m + n,sizeof(int),int_compare);
}

可以看到代码逻辑还是相对简单的，并且效率也很高,因为这里的qsort使用的是快排，时间复杂度仅仅是O(NlogN)，空间复杂度是O(1)，但是我们下面还有一个办法使它更快一点,那就还是我们的双指针法

方法2（双指针）

其实我们这三道题都很类似，所以双指针很吃香，只不过在这道题中，我们有两个数组需要合并，我们还是可以试着用之前的思路来思考一下这个题，上面的题是一个数组，而这一道题是两个数组，那我就可以定义两个指针src1 和 src2

之前的思路就是，如果碰到相同的元素，或者题目给出的元素，我们就把他给跳过，使用后面的元素把它覆盖，那这道题就有一些不一样的地方

首先第一个思路就是src1指向nums1的第一个元素，src2指向nums2的第一个元素，由于最后的结果要保存在nums1中，所以我们把dest定义在nums1中，指向nums1的第一个位置

随后我们比较src1指向的元素和src2指向的元素哪个小，哪个小就把它放到dest的位置上，然后让dest++，然后src1++或者src2++，最后循环这个步骤

但是我们最后发现这个思路有点问题，问题出在nums1数组中，因为如果我们直接把数据放在dest，也就是从nums1数组的开头开始存放数据，会导致原本的nums1数组的数据被覆盖，我们举个例子，如图：

这个时候我们发现问题了，nums1中的数据会被覆盖，所以第一种思路并不可行，那么应该怎样改进，避免数据被覆盖呢？这个时候我们不放换一个思路，倒过来想，既然放小的不行，那咱们就放大的，也就是 从nums1的最后开始放数据，也就是让我们的dest指向nums1的最后一个位置

因为我们要保证nums1最后排序成相对递增，最后一个位置就要放最大值，我们可以让src1 和 src2分别指向nums1 和 nums2的最后一个元素，然后比较谁大谁就放在dest的位置

然后让dest–，以及src1- -或者src2- -，就这样一直找大放在dest的位置，循环条件就是要让src1和src2都大于0，因为都是数组下标，都不能越界

可以看到我们这里将两个数组合并到了nums1中，让数组nums1有序了，但是其实有一个问题，如果我们最后是src2先越界，那么说明nums2数组中的数据已经全部放入nums1了，循环结束了，剩下的nums1的数据也已经保持了有序，所以src2首先越界代码没有问题

但是有可能下一次src1首先越界，说明nums1中原本的有效的元素已经放在nums1数组后面了，循环结束了，但是nums2数组还没有放完呀，这个时候就会出错，所以我们还需要在这个循环结束后用一个新的循环判断一下

如果src2还大于等于0，说明nums2数组中的内容还没有全部移动到nums1中，此时我们只需要循环地让数组nums2中的元素移动到nums1的dest位置，接下来我们的代码才能完全没问题，如下：

void merge(int* nums1, int nums1Size, int m, int* nums2, int nums2Size, int n) 
{
    int src1 = m - 1;
    int src2 = n - 1;
    int dest = m + n - 1;//nums1的最后一个位置
    while(src1 >= 0 && src2 >= 0)
    {
        //单纯的比大小，谁大就放谁
        if(nums1[src1] < nums2[src2])
        {
            nums1[dest--] = nums2[src2--];
        }
        else
        {
            nums1[dest--] = nums1[src1--];
        }
    }
    //如果nums2还没有走完
    while(src2 >= 0)
    {
        //将nums2的元素全部放进nums1的dest位置
        nums1[dest--] = nums2[src2--];
    }
}

成功拿下，我们再来分析一下这个代码的时间复杂度和空间复杂度，可以发现我们虽然有两个循环，但是实际上深入计算会发现两个循环的次数加起来为O(N)，所以时间复杂度是标准的O(N)

并且由于申请的是有限个空间，所以空间复杂度是O(1)，我们就可以看出来了，虽然我们的快排很快，时间复杂度仅为O(N * logN)，但是我们的双指针更快，只有O(N)

那么今天就分享到这里，希望大家有所收获，也不枉博主码这么多字,bye~~