温馨提示×

温馨提示×

您好,登录后才能下订单哦!

密码登录×
登录注册×
其他方式登录
点击 登录注册 即表示同意《亿速云用户服务条款》

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

发布时间:2022-04-11 17:33:26 来源:亿速云 阅读:201 作者:zzz 栏目:开发技术

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

1、移除元素

题目:

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

思路:

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

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

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

 此法有个缺陷,题目中明确指出使用空间复杂度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

此法是在法二的基础上进行的升级,法二需要开辟额外数组,此法直接原数组改动。首先定义两个变量src和dst为0,都作为数组nums的下标,依次遍历src看nums[src]是否为val,若不是,将其赋给下标dst,再src++,dst++。若nums[src]=nums[dst],则只把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、删除有序数组中的重复项

题目:

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

思路:

双指针(不额外开数组)

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

注意:

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

画图演示:

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

代码如下:

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

3、合并两个有序数组

链接直达:

合并两个有序数组

题目:

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

思路:

法一: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数组上去。

画图演示:

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

 代码如下:

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语言经典顺序表实例分析”这篇文章的内容,相信大家都有了一定的了解,希望小编分享的内容对大家有帮助,若想了解更多相关的知识内容,请关注亿速云行业资讯频道。

向AI问一下细节

免责声明:本站发布的内容(图片、视频和文字)以原创、转载和分享为主,文章观点不代表本网站立场,如果涉及侵权请联系站长邮箱:is@yisu.com进行举报,并提供相关证据,一经查实,将立刻删除涉嫌侵权内容。

AI