时间复杂度、空间复杂度实践练习(力扣OJ)

这篇具有很好参考价值的文章主要介绍了时间复杂度、空间复杂度实践练习(力扣OJ)。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

目录

文章目录

前言

题目一:轮转数组

 思路一:

 思路二:

思路三:

题目二:消失的数字

 思路一:

 思路二:

 思路三:

 题目三:移除元素

思路:

总结



 

前言

       想要编写高效的算法,了解时间复杂度是至关重要的。在本文中,我们将介绍一些时间复杂度和空间复杂度的练习,通过实际例子帮助您分析程序的时间复杂度和空间复杂度 ,前边已经了解过,复杂度是评价一个程序好坏标准,今天我们切身体验一下数据结构入门刷题。如何写出好的程序。


题目一:轮转数组

题目如下:

时间复杂度、空间复杂度实践练习(力扣OJ),leetcode,算法,数据结构

 题目给出的示例如下:

时间复杂度、空间复杂度实践练习(力扣OJ),leetcode,算法,数据结构

 思路一:

         没做过类似题目的人,大多数人思路或许是这样的:将数组最好一个元素保存,其他元素向后移动,再将保存的元素放在最前边。这也只是这道题的其中一种解题思路。但这个思路在力扣上过不去的。

        我们来分析一下这个思路:我们知道数组元素个数假设为n,但要将其他元素向后移动就需要进行n-1次,此外如果遇到最坏的情况我们需要轮转n-1次(执行n次就是原数组,n+1次就等价于轮转一次),每次执行n-1次,它的时间复杂度就是O(N^2),空间复杂度为O(1)。由此可见这个思路的效率很低,所以这个思路我就不再实现。

 思路二:

        我们观察一下初始数组和输出数组的特点,就可以很容易的想到这个思路:轮转几次就把后几个数字移到前边,把前边的部分移到后边。这个方法简单粗暴。

时间复杂度、空间复杂度实践练习(力扣OJ),leetcode,算法,数据结构

 代码实现:

void rotate(int* nums, int numsSize, int k)
{
    int *tmp = (int*)malloc( sizeof(int) * numsSize );
    k %= numsSize;
    memcpy(tmp,nums+numsSize-k,sizeof(int)*k);
    memcpy(tmp+k,nums,sizeof(int)*(numsSize-k));
    memcpy(nums,tmp,sizeof(int)*numsSize);
    free(tmp);
}

时间复杂度、空间复杂度实践练习(力扣OJ),leetcode,算法,数据结构

 它的时间复杂度为O(N),空间复杂度也为O(N)。用空间来换取效率,这个思路也并不是最优解。

思路三:

        我们也可以通过将数组元素逆置的方法来达到轮转的效果思路如下:

时间复杂度、空间复杂度实践练习(力扣OJ),leetcode,算法,数据结构

 代码实现:

void reverse(int* nums, int star, int end) {
    while (star < end) {
        int temp = nums[star];
        nums[star] = nums[end];
        nums[end] = temp;
        star++;
        end--;
    }
}

void rotate(int* nums, int numsSize, int k) {
    k %= numsSize;
    reverse(nums, 0, numsSize - 1);
    reverse(nums, 0, k - 1);
    reverse(nums, k, numsSize - 1);
}

时间复杂度、空间复杂度实践练习(力扣OJ),leetcode,算法,数据结构

         这个思路的时间复杂度为O(N),空间复杂度为O(1)。这个思路才是这道题的最优解。

题目二:消失的数字

题目描述:

时间复杂度、空间复杂度实践练习(力扣OJ),leetcode,算法,数据结构

 思路一:

        题目中说到数组包含从0到n的所有整数,但缺少其中一个。那我们就可以先对数组的元素进行排序,然后遍历,如果下一个数据不等于下一个数加一,那么下一个数就是消失的数字。思路理清之后,我们可以先看一下这个思路的复杂度如何。

         复杂度也取决于排序的方法,最优的排序是使用qsort排序,时间复杂度为O(logN*N)。然后是遍历,根据大O的渐进表示法,估算出它的时间复杂度为O(logN*N)。可见这个方法的效率并不高,我们对于复杂度高的方法就不再实现。

 思路二:

         数组中的数据包含0到n所有整数,但缺失某一个,那我们就可以使用这个思路,将0到n看作一个等差数列,使用等差数列求和公式求和,最后将这个值依次减去数组中元素,最后的结果就是消失的数字。根据这个思路我们可以分析出它的时间复杂度是O(N)。

代码实现:

int missingNumber(int* nums, int numsSize){
   int n=numsSize;
   int ret=n*(n+1)/2;
   for(int i=0;i<n;i++)
   {
       ret-=nums[i];
   }
   return ret;
}

时间复杂度、空间复杂度实践练习(力扣OJ),leetcode,算法,数据结构

 思路三:

        使用异或的方法,两个相同的数字异或的结果是0,并且异或符合乘法结合律,例如:1^2^1等于2,1^1^2也等于2。根据异或的这个特性,我们可以先异或0到n的所有数字,在将数组中所有元素依次异或,最终的结果就是消失的数字,根据思路我们可以估算出这个方法的时间复杂度也是O(N)。

代码实现:

int missingNumber(int* nums, int numsSize){
int ret=0;
for(int i=0;i<numsSize;i++)
{
 ret^=i;       
 ret^=nums[i];
}
return ret^numsSize;
}

 异或0到n的数字与数组同时异或就会少异或最后一个数字,所有最后返回时进行异或。

 时间复杂度、空间复杂度实践练习(力扣OJ),leetcode,算法,数据结构

 题目三:移除元素

题目描述:

时间复杂度、空间复杂度实践练习(力扣OJ),leetcode,算法,数据结构

示例与说明:

 时间复杂度、空间复杂度实践练习(力扣OJ),leetcode,算法,数据结构

         题目要求空间复杂度是O(1),并且数组还是无序的,返回的数组还要求是原来的顺序。看对于没做过类似题目的朋友,到这道题或许会感到头大,能想到的方法也大多数都很复杂。

        不要在意力扣的题目难度标签,力扣题目显示为简单的题目不一定简单,但难度标为中等或难的题目题解思路一定复杂。

思路:

        这里我向大家介绍一种很简单的方法,这种思路在其他很多场景中也是很常用的。我们可以遍历这个数组,如果数组中的元素与要删除的val值不相等就插入到数组中,如果相等就往后走。

 假设要删除2。

 时间复杂度、空间复杂度实践练习(力扣OJ),leetcode,算法,数据结构

         0不等于2就插入数组,继续下一个,1与2不相等插入数组,继续向后遇到2不插入,原数组继续向后走。这个思路它的时间复杂度是O(N)。至于空间复杂度,题目要求空间复杂度为O(1),但这个方法显然空间复杂度是O(N),但是我们好好想一想,我们如果不选择创建新的数组,直接在原数组例插入,这样是否也可以。答案是可行的。依据这个思路我们将代码实现。

代码如下:

int removeElement(int* nums, int numsSize, int val) {
    int sz = numsSize;
    int pos=0;
    for (int i = 0; i < numsSize; i++)
    {
        if (val != nums[i])
            nums[pos++]=nums[i];
        else
            sz--;
    }
    return sz;
}

时间复杂度、空间复杂度实践练习(力扣OJ),leetcode,算法,数据结构

 方法简单快捷。


总结

        时间复杂度和空间复杂度有是衡量算法效率和算法好坏的重要指标,它直接关系到算法的执行速度和资源消耗。在本篇博客中,我们将通过了一系列时间复杂度和空间复杂度实战应用的练习,可以帮助您提升对算法效率的理解和应用能力,好的,到这里就要结束了,最后,感谢阅读!文章来源地址https://www.toymoban.com/news/detail-623992.html

到了这里,关于时间复杂度、空间复杂度实践练习(力扣OJ)的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 【数据结构】算法的时间复杂度和空间复杂度(下)(附leetcode练习题)

    ☃️个人主页:fighting小泽 🌸作者简介:目前正在学习C语言和数据结构 🌼博客专栏:数据结构 🏵️欢迎关注:评论👊🏻点赞👍🏻留言💪🏻 空间复杂度也是一个数学表达式,是对一个算法在运行过程中 临时占用的额外的存储空间大小的量度 。 空间复杂度不是程序占用

    2023年04月19日
    浏览(82)
  • 【数据结构】算法的时间复杂度和空间复杂度 (上)(附leetcode练习题)

    ☃️个人主页:fighting小泽 🌸作者简介:目前正在学习C语言和数据结构 🌼博客专栏:数据结构 🏵️欢迎关注:评论👊🏻点赞👍🏻留言💪🏻 如何衡量一个算法的好坏呢?比如对于以下斐波那契数列: 斐波那契数列的递归实现方式非常简洁,但简洁一定好吗?那该如何

    2023年04月22日
    浏览(60)
  • C/C++数据结构之时间复杂度和空间复杂度详细解析以及力扣刷题

    个人主页:点我进入主页 专栏分类:C语言初阶      C语言程序设计————KTV       C语言小游戏     C语言进阶 C语言刷题       数据结构初阶 欢迎大家点赞,评论,收藏。 一起努力,一起奔赴大厂。 目录  1.前言 2.算法的效率 2.1时间复杂度  2.1.1时间复杂度的定义

    2024年02月06日
    浏览(43)
  • 时间复杂度和空间复杂度

    时间复杂度和空间复杂度是用来评估算法性能的两个重要指标。 时间复杂度(Time Complexity)是衡量算法执行时间随输入规模增长而增长的度量。它表示了算法解决问题所需的时间量级。常见的时间复杂度有: 常数时间复杂度 O(1):无论输入规模的大小,算法的执行时间都是固

    2024年01月17日
    浏览(47)
  • 算法的时间复杂度与空间复杂度

    1.算法效率 2.时间复杂度 3.空间复杂度 4.复杂度oj题目 1.算法效率 1.1 如何衡量一个算法的好坏 一辆车的好坏我们可以从价格,油耗...... 方面来衡量,但衡量一个算法的好坏我们该从哪一个方面入手呢?比如斐波那契数列: 斐波那契数列的递归实现方式非常简洁,但简洁一定

    2024年02月15日
    浏览(83)
  • 【算法基础】时间复杂度和空间复杂度

    1 算法的评价 2 算法复杂度 2.1 时间复杂度(Time Complexity) 2.1.1 如何计算时间复杂度: 2.1.2 常见的时间复杂度类别与示例 2.2 空间复杂度 2.2.1 如何计算空间复杂度 2.2.2 常见的空间复杂度与示例 3 时间复杂度和空间复杂度计算示例 例子1:计算数组中所有元素的和。 例子2:快

    2024年02月08日
    浏览(56)
  • 算法的时间复杂度和空间复杂度

    目录 本章重点 一 时间复杂度 2.1 时间复杂度的概念 2.2 大O的渐进表示法 2.3 常见的时间复杂度的计算 二 空间复杂度 三 常见复杂度对比 四 复杂度的oj练习 4.1 消失的数字 4.2 旋转数字 每一天都是人生限定,每一天都值得100%努力 (1)算法效率(2)时间复杂度(3)空间复

    2024年02月01日
    浏览(47)
  • 什么是时间复杂度和空间复杂度

    🍕博客主页:️自信不孤单 🍬文章专栏:数据结构与算法 🍚代码仓库:破浪晓梦 🍭欢迎关注:欢迎大家点赞收藏+关注 数据结构(Data Structure)是计算机存储、组织数据的方式,指相互之间存在一种或多种特定关系的数据元素的集合。 算法(Algorithm):就是定义良好的计算过程

    2023年04月15日
    浏览(42)
  • 算法之【时间复杂度】与【空间复杂度】

    目录 一、算法 1、算法定义 2、两种算法的比较 3、算法的特性 4、算法设计的要求 二、算法的复杂度 1、时间复杂度 1.1定义 1.2大O的渐近表示法 1.3推导大O阶方法 1.4最坏情况与平均情况 1.5常见的时间复杂度计算示例 🍂常数阶: 🍂线性阶:  🍂对数阶: 🍂平方阶: 2、空间

    2024年02月05日
    浏览(57)
  • 数据结构(时间复杂度,空间复杂度)

    算法的时间复杂度是一个数学函数,算法中的基本操作的执行次数,为算法的时间复杂度。 1.大O的表示法 2.推导大O表示法 1、用常数1取代运行时间中的所有加法常数。 2、在修改后的运行次数函数中,只保留最高阶项。 3、如果最高阶项存在且不是1,则去除与这个项目相乘的

    2024年02月07日
    浏览(49)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包