C语言经典顺序表实例分析

这篇“C语言经典顺序表实例分析”文章的知识点大部分人都不太理解，所以小编给大家总结了以下内容，内容详细，步骤清晰，具有一定的借鉴价值，希望大家阅读完这篇文章能有所收获，下面我们一起来看看这篇“C语言经典顺序表实例分析”文章吧。

1、移除元素

题目：

思路：

法一：依次挪动数据进行覆盖

从第一个数据开始进行依次遍历，如同示例1，依次遍历数组，找到移除的元素2就把后面的数据往前挪动进行覆盖，如图所示：

 此法有个缺陷，题目中明确指出使用空间复杂度O(1)的方法解决此问题，而此法的空间复杂度刚好为O(1)，可以解决，不过考虑周全些，时间复杂度在情况最坏时为O(N^2)，出现全是val的情况，将会挪动n-1+n-2+……出现了等差数列，时间复杂度为O(N^2)，此法不是最优，换。

法二：双指针1.0

依次遍历原数组，看是不是val，把不是val的值，拷贝到新数组，此法的时间复杂度是O(N)，空间复杂度也是O(N)，可是题目明确指出空间复杂度要为O(1)，所以此法不行，但是仔细想想，如果继续用此法双指针，但是不另开数组，就在原数组上改动可否呢？，由此引出双指针2.0

法三：双指针2.0

此法是在法二的基础上进行的升级，法二需要开辟额外数组，此法直接原数组改动。首先定义两个变量class="lazy" data-src和dst为0，都作为数组nums的下标，依次遍历class="lazy" data-src看nums[class="lazy" data-src]是否为val，若不是，将其赋给下标dst，再class="lazy" data-src++，dst++。若nums[class="lazy" data-src]=nums[dst]，则只把class="lazy" data-src++，dst不动，最后再把长度dst返回即可。

代码如下：

int removeElement(int* nums, int numsSize, int val){    int dst=0;    int str=0;    while(str<numsSize)    {        if(nums[str]==val)        {            str++;        }        else        {            nums[dst]=nums[str];            dst++;            str++;        }    }    return dst;}

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

题目：

思路：

双指针（不额外开数组）

此题和上题类似，同样可以采用双指针，并在原数组进行改动，只需要定义两个变量dst和class="lazy" data-src作为数组nums的下标，但此时做出小变动，把class="lazy" data-src从下标1开始，而dst从下标0开始。让nums[class="lazy" data-src]每次和它前一个也就是nums[class="lazy" data-src-1]相比较，如果相等，则class="lazy" data-src++，若不等就把nums[class="lazy" data-src-1]赋给nums[dst]，再dst++，class="lazy" data-src++。

注意：

执行完上述操作后，还存在一个问题，那就是没把class="lazy" data-src的最后一个下标的值放到nums[dst]里头去，就如同本题的示例，当class="lazy" data-src走到倒数第二个值3的时候，和前一个3相等，此时需要++class="lazy" data-src，现在nums[class="lazy" data-src]就是4，和前一个值不相等，把3赋给nums[dst]，此时class="lazy" data-src再++到空了，没有数据和4比较了，越界，所以4就漏掉了。在如同当后面2个数字同为3的时候，因为一直相等，class="lazy" data-src同样+到空，3同样漏掉，所以无论哪种情况，都要把最后一个数字移到nums[dst]上

画图演示：

代码如下：

int removeDuplicates(int* nums, int numsSize){    int dst=0;    int class="lazy" data-src=1;    while(class="lazy" data-src<numsSize)    {        if(nums[class="lazy" data-src]==nums[class="lazy" data-src-1])        {            class="lazy" data-src++;        }        else        {            nums[dst]=nums[class="lazy" data-src-1];            dst++;            class="lazy" data-src++;        }    }    nums[dst]=nums[numsSize-1];    dst++;    return dst;}

3、合并两个有序数组

链接直达：

合并两个有序数组

题目：

思路：

法一：memmove + sort排序（冒泡、qsort等）

此法确实可以，不过当题目中明确指出要用时间复杂度O(N)的方法解决此问题的话，那么此法就行不通了，因为冒泡的时间复杂度为O(N^2)，而qsort的时间复杂度为O(N*logN)。均不是O(N)，所以得换。

法二：归并1.0

依次比较，每次把小的放到归并数组。此法需要开辟第三方数组a。其次，需要定义 i ，j ，dst 三个变量分别用来表示数组nums1，nums2，a的第一个下标，如果nums1[ i ]<nums[ j ]，则a[dst++]=nums1[ i++ ]，反之a[dst++]=nums2[ i++ ]，依次遍历下去，当其中一个走完了，就把剩下的全部放到a数组里头去，此法的最大问题就是需要额外开辟一个数组，以空间换时间，导致空间复杂度为O(N)，但是我们在基于此法的基础上可以进行升级，如下：

法三：归并2.0

此法是在法二的基础上进行升级，直接在nums1原数组上进行改动，思想和法二差不多。不过有个需要改变的地方，法二是正着遍历数组，但是此法则需要倒着来遍历数组。那么此时的 i 变量就是nums1数组第m-1个下标，j变量就是nums2数组第n-1个下标，dst变量就是nums1数组最后一个元素下标（m+n-1）。实现原理同法二，不做过多赘述。注意：如果nums2数组的下标 j 先结束，那么nums1剩下的数组刚好排在前面，不需要动，如果是nums1数组的下标 i 先结束，则需要把nums2数组剩余的值赋到nums1数组上去。

画图演示：

 代码如下：

void merge(int* nums1, int nums1Size, int m, int* nums2, int nums2Size, int n){    int i=m-1;    int j=n-1;    int dst=m+n-1;    while(i>=0&&j>=0)    {        if(nums1[i]>nums2[j])        {            nums1[dst--]=nums1[i--];        }        else        {            nums1[dst--]=nums2[j--];        }    }    while(j>=0)    {        nums1[dst--]=nums2[j--];    }}

以上就是关于“C语言经典顺序表实例分析”这篇文章的内容，相信大家都有了一定的了解，希望小编分享的内容对大家有帮助，若想了解更多相关的知识内容，请关注编程网行业资讯频道。