【刷题系列】顺序表OJ题

小明的c++笔记本 2023-07-18 原文

文章题目来源力扣
🎈力扣（LeetCode）全球极客挚爱的技术成长平台
LeetCode官网：https://leetcode-cn.com/problem-list/e8X3pBZi/

✨目录

移除元素
删除排序数组中的重复项
合并两个有序数组

1.移除元素

来源：力扣（LeetCode）
题目链接：https://leetcode.cn/problems/remove-element/

思路一：
遇到val值，直接把val删除，运用顺序表的删除，把后面的值往前覆盖掉val
优点：学了顺序表后容易想到
缺点：时间复杂度O(N^2)——>效率太低(在LeetCode上可能过不了)

思路一不作代码实现！！！

思路二：
可以另开一个数组，将不是val的值拷贝到新数组里，然后再覆盖拷贝回去
（典型的以空间换时间）
优点：时间复杂度O(N)
缺点：空间复杂度为O(N)不符合要求

代码实现：

int removeElement(int* nums, int numsSize, int val){
    if(nums==NULL || numsSize==0)//特殊值处理
        return 0;
    int a[numsSize];
    int i=0;
    int j=0;
    // 把不是val的值拷贝出来
    while(i<numsSize)
    {
        if(nums[i]!=val)
        {
            a[j++]=nums[i++];
        }
        else
            i++;
    }
    //覆盖拷贝回去
    i=0;
    while(i<j)
    {
        nums[i]=a[i];
        i++;
    }
    return j;
}

思路三：（优解）
我们可以在思路二的想法上再优化一点，思路二时间复杂度已经是最优了，但是要开辟一个数组来拷贝。
那我们能不能不开辟新数组，直接在原数组中拷贝呢？
答案是可以的！我们把原数组既当拷贝数组，又当目标数组
优点：时间复杂度O(N),空间复杂度O(1)
实现方法：
定义两个下标，一个des，一个src，遇到val值，把src往后找移，des在val值中不动，直到src找到一个不是val值的数，然后把src指向的数覆盖拷贝到des中，然后des往后移一步，src进行找不是val值重复上面工作。

代码代码实现

int removeElement(int* nums, int numsSize, int val){

    int des=0,src=0;
    while(src<numsSize)
    {
        if(nums[src]!=val)//把非val的值覆盖val值
        {
            nums[des++]=nums[src++];
        }
        else
        {
            src++;
        }
    }
    return des;
}

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

来源：力扣（LeetCode）
题目链接：https://leetcode.cn/problems/merge-sorted-array

思路：
这题跟上面移除元素有异曲同工之妙，你可以尝试用上面的思路一和思路二来解决这个题，
我在这里只演示思路三

实现方法： 因为它们是有序的，所以我们可以像上面的思路三一样，在原地覆盖拷贝，把其中一个重复的值删掉！

代码实现

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

3.合并两个有序数组

来源：力扣（LeetCode）
题目链接：https://leetcode.cn/problems/merge-sorted-array

思路一：
把nums2数组中的元素拷贝到nums1后面，然后排序
优点：容易想到
缺点：排序耗费时间大，我们所熟悉的排序中，最快的不过是快速排序，但它是时间复杂度是
O(N*logN)

代码实现：自行实现！

思路二：
我们可以想想，因为它本身就是有序的，我们是不是可以这样
开一个新数组，分别比较两数组的值，把小的取下来尾插到新数组中，最后再拷贝回nums1
优点：时间复杂度O(N+M)
缺点：空间复杂度O(N+M)

代码实现：自行实现！

思路三：（优解）
吸取思路二中的思路，我们可不可以在原地把它搞定呢？
答案是可以的！
因为nums1中的后面的位置足已把nums2放进去，我们可以把nums1的后面位置当作新数组，
但是我们不能取小了，要转换思路，取大的放在nums1后面！！！

但是这样的方法会分两种情况：

情况一：nums2先结束
情况二：nums1先结束
代码实现：

void merge(int* nums1, int nums1Size, int m, int* nums2, int nums2Size, int n){
    int end1=m-1, end2=n-1,i=m+n-1;

    while( end1>=0 && end2>=0 )
    {
        if(nums1[end1] > nums2[end2] )
        {
            nums1[i--]=nums1[end1--];
        }
        else
        {
            nums1[i--]=nums2[end2--];
        }
    }

    //num2没结束
    while(end2>=0)
    {
        nums1[i--]=nums2[end2--];
    }
}

系列顺序 span class token leetcode 算法数据结构 c语言

有关【刷题系列】顺序表OJ题的更多相关文章

python - 如何使用 Ruby 或 Python 创建一系列高音调和低音调的蜂鸣声？ - 2
关闭。这个问题是opinion-based.它目前不接受答案。想要改进这个问题？更新问题，以便editingthispost可以用事实和引用来回答它.关闭4年前。Improvethisquestion我想在固定时间创建一系列低音和高音调的哔哔声。例如:在150毫秒时发出高音调的蜂鸣声在151毫秒时发出低音调的蜂鸣声200毫秒时发出低音调的蜂鸣声250毫秒的高音调蜂鸣声有没有办法在Ruby或Python中做到这一点？我真的不在乎输出编码是什么(.wav、.mp3、.ogg等等)，但我确实想创建一个输出文件。
ruby-on-rails - 使用一系列等级计算字母等级 - 2
这里是Ruby新手。完成一些练习后碰壁了。练习:计算一系列成绩的字母等级创建一个方法get_grade来接受测试分数数组。数组中的每个分数应介于0和100之间，其中100是最大分数。计算平均分并将字母等级作为字符串返回，即“A”、“B”、“C”、“D”、“E”或“F”。我一直返回错误:avg.rb:1:syntaxerror,unexpectedtLBRACK,expecting')'defget_grade([100,90,80])^avg.rb:1:syntaxerror,unexpected')',expecting$end这是我目前所拥有的。我想坚持使用下面的方法或.join，
ruby - Chef 执行非顺序配方 - 2
我遵循了教程http://gettingstartedwithchef.com/,第1章。我的运行list是"run_list":["recipe[apt]","recipe[phpap]"]我的phpapRecipe默认Recipeinclude_recipe"apache2"include_recipe"build-essential"include_recipe"openssl"include_recipe"mysql::client"include_recipe"mysql::server"include_recipe"php"include_recipe"php::modul
【鸿蒙应用开发系列】- 获取系统设备信息以及版本API兼容调用方式 - 2
在应用开发中，有时候我们需要获取系统的设备信息，用于数据上报和行为分析。那在鸿蒙系统中，我们应该怎么去获取设备的系统信息呢，比如说获取手机的系统版本号、手机的制造商、手机型号等数据。1、获取方式这里分为两种情况，一种是设备信息的获取，一种是系统信息的获取。1.1、获取设备信息获取设备信息，鸿蒙的SDK包为我们提供了DeviceInfo类，通过该类的一些静态方法，可以获取设备信息，DeviceInfo类的包路径为：ohos.system.DeviceInfo.具体的方法如下：ModifierandTypeMethodDescriptionstatic StringgetAbiList()Obt
阿里云RDS——产品系列概述 - 2
基础版云数据库RDS的产品系列包括基础版、高可用版、集群版、三节点企业版，本文介绍基础版实例的相关信息。RDS基础版实例也称为单机版实例，只有单个数据库节点，计算与存储分离，性价比超高。说明RDS基础版实例只有一个数据库节点，没有备节点作为热备份，因此当该节点意外宕机或者执行重启实例、变更配置、版本升级等任务时，会出现较长时间的不可用。如果业务对数据库的可用性要求较高，不建议使用基础版实例，可选择其他系列（如高可用版），部分基础版实例也支持升级为高可用版。基础版与高可用版的对比拓扑图如下所示。优势性能由于不提供备节点，主节点不会因为实时的数据库复制而产生额外的性能开销，因此基础版的性能相对于
ruby-on-rails - 在 RSpec 中，如何以任意顺序期望具有不同参数的多条消息？ - 2
RSpec似乎按顺序匹配方法接收的消息。我不确定如何使以下代码工作:allow(a).toreceive(:f)expect(a).toreceive(:f).with(2)a.f(1)a.f(2)a.f(3)我问的原因是a.f的一些调用是由我的代码的上层控制的，所以我不能对这些方法调用添加期望。最佳答案 RSpecspy是测试这种情况的一种方式。要监视一个方法，用allowstub，除了方法名称之外没有任何约束，调用该方法，然后expect确切的方法调用。例如:allow(a).toreceive(:f)a.f(2)a.f(1)
ruby - 按数字(从大到大)然后按字母(字母顺序)对对象集合进行排序 - 2
我正在构建一个小部件来显示奥运会的奖牌数。我有一个“国家”对象的集合，其中每个对象都有一个“名称”属性，以及奖牌计数的“金”、“银”、“铜”。列表应该排序:1.首先是奖牌总数2.如果奖牌相同，按类型分割(金>银>铜，即2金>1金+1银)3.如果奖牌和类型相同，则按字母顺序子排序我正在用ruby做这件事，但我想语言并不重要。我确实找到了一个解决方案，但如果感觉必须有更优雅的方法来实现它。这是我做的:使用加权奖牌总数创建一个虚拟属性。因此，如果他们有2个金牌和1个银牌，加权总数将为“3.020100”。1金1银1铜为“3.010101”由于我们希望将奖牌数排序为最高的，因此列表按降序排
ruby - 以随机顺序将数组拆分为多个数组 - Ruby - 2
我试图在每次运行时以随机顺序将一个名称数组拆分为多个数组。我知道如何拆分它们:name_array=["bob","john","rob","nate","nelly","michael"]array=name_array.each_slice(2).to_a=>[["bob","john"],["rob","nate"],["nelly","michael"]]但是，如果我希望它每次都以随机顺序吐出它们怎么办？最佳答案在做同样的事情之前，打乱数组。(Array#shuffle)name_array.shuffle.each_s
ruby - 从结束值创建一系列字符串 - 2
我使用irb。下面是我写的代码。“斧头”..“bc”我期待"ax""ay""az""ba"bb""bc"但结果只是“斧头”..“bc”我该如何纠正？谢谢。最佳答案 >puts("ax".."bc").to_aaxayazbabbbc 关于ruby-从结束值创建一系列字符串，我们在StackOverflow上找到一个类似的问题： https://stackoverflow.com/questions/7617092/
ruby - 根据给定顺序对数字数组进行排序 - 2
我有两个数组。第一个数组包含排序顺序。第二个数组包含任意数量的元素。我的属性是保证第二个数组中的所有元素(按值)都在第一个数组中，而且我只处理数字。A=[1,3,4,4,4,5,2,1,1,1,3,3]Order=[3,1,2,4,5]当我对A进行排序时，我希望元素按照Order指定的顺序出现:[3,3,3,1,1,1,1,2,4,4,4,5]请注意，重复是公平的游戏。A中的元素不应更改，只能重新排序。我该怎么做？最佳答案 >>source=[1,3,4,4,4,5,2,1,1,1,3,3]=>[1,3,4,4,4,5,2,1,1

【刷题系列】顺序表OJ题

1.移除元素

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

3.合并两个有序数组

有关【刷题系列】顺序表OJ题的更多相关文章

随机推荐