专栏首页算法channel昨天的文章,有朋友给出"更好的"解法,其实并不是...

昨天的文章,有朋友给出"更好的"解法,其实并不是...

昨天推送一道题目分析,一方面学习一个颇具特色的数组,它的取值不大于数组长度;另一方面通过这道题充分体会算法分析、逻辑推理的重要性。只有做好充分的分析,才可能写出对这道题的时间复杂度O(n),空间复杂度O(1)的解。

时间、空间复杂度关乎程序的性能,时间复杂度低跑的就快,空间复杂度小占用的内存空间小。谁会乐意手机的一个app动不动就占用我们大几百M的内存呢。

所以,程序的性能评判,就是对以上两个指标的评判,要给予很高的重视。

昨天几位朋友文章下的留言比较典型,在此不是有意针对,而是把问题拿出来,纠正有一样认识的朋友。

写文章帮助大家共同提高,是一直不变的目标。

这是昨天的文章:

我分析的一道笔试题,留言说说你是否看懂了?

下面是留言区几位朋友给出的解题思路:

1

依次遍历列表,通过count统计每个元素的出现次数。

大家可能有一个误区:认为调用API时间复杂度就为O(1),很明显并不是。

我们可想一下count的时间复杂度,如果换成我们自己去实现某个元素在列表中的出现次数,一般肯定是遍历一遍统计出结果,时间复杂度为O(n).

所以,外层遍历列表,内层count,时间复杂度为

O(n^2)

2

先排序一遍,一趟循环就可以了。

有这种想法的朋友,要先问问自己排序的时间复杂度为多少?O(nlogn)

总结

昨天文章给出的解法:时间复杂度为O(n),空间复杂度为O(1),应该是最好的求解方法之一。它之所以能到最好,是因为充分利用了列表取值范围:

1\leq nums[i] \leq len(nums)

这个条件。

而上面的两个解法,完全没有考虑数组的这个特点,自然就难以达到最优。

这体现了算法的重要性,开展算法分析的必要性。

我们的目标:追求极致,多角度深入剖析一道题,并应用到实际工作中。

加油!

写于 2020.7.10. 早6点50

本文分享自微信公众号 - Python与机器学习算法频道(alg-channel),作者:振哥

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2020-07-10

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 面试编程题1:充分利用已知的计算条件

    上篇说到,要想在面试中处于不败之地,不能靠简单的刷题,而是要学会分析题目,尽可能找出内在规律,思维要敏捷。要想达到这种功力,需要平时多注意进行有意识的训练总结。

    double
  • 一道伤脑筋的算法题 亮了

    一个数组,求除了某元素自身位置之外的其他元素累积相乘,返回一个同长度的数组。有两个要求比较苛刻: 1) 不能用除法 2) 时间复杂度O(n),空间复杂度O(1)...

    double
  • Python定做一个计算器,小而美哒~

    qt 设计器提供的常用控件基本都能满足开发需求,通过拖动左侧的控件,很便捷的就能搭建出如下的UI界面,比传统的手写控件代码要方便很多。

    double
  • 数据结构与算法 1-4 常见时间复杂度与大小关系

    本系列是我在学习《基于Python的数据结构》时候的笔记。本小节主要介绍一些常见的时间复杂度以及它们之间的大小关系。

    触摸壹缕阳光
  • 数据结构算法入门--一文了解什么是复杂度

    最近会开始更新一个数据结构算法的学习系列,同时不定期更新 leetcode 的刷题。

    kbsc13
  • 02 复杂度分析_pythoner学习数据结构与算法系列

    设计算法时,时间复杂度要比空间复杂度更容易出问题,所以一般情况一下我们只对时间复杂度进行研究。一般面试或者工作的时候没有特别说明的话,复杂度就是指时间复杂度...

    诡途
  • 常用算法解析

    算法基础:概念,时间复杂度,空间复杂度,常见算法以及复杂度计算 ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?...

    wangxl
  • 笔试常考题型之时间复杂度

    Zoctopus
  • 笔试常考题型之时间复杂度

    Zoctopus
  • 数据结构和算法

    10个算法:递归、排序、二分查找、搜索、哈希算法、贪心算法、分治算法、回溯算法、动态规划、字符串匹配算法。

    分母为零

扫码关注云+社区

领取腾讯云代金券