Mickey's Blog ·

【leetCode】两个排序数组的中值(Median of Two Sorted Arrays)day4

今天呢是我们这道题的最后一天,这道题虽然做了很多天但是我还是产生了很多感觉,先说结果,方案三十我能想到最简单的实现方法,我直接实现,时间大概是800ms,然后我又继续尝试方案二,这次我吸取了教训,交叉使用了方案三的一部分代码,最终实现了只构建少部分数据,取到中位数,但是时间也是800ms左右,我不禁开始怀疑,怎么这两个方案没什么差别,而且代码量都不小,方案三150行左右,方案二137行,直到我去看了这道题的性能最优解,我知道了差距和问题,先贴出最优解代码

1.png

这段代码我当时看到时是懵逼的,他用了27行,(远答案在变量声明和返回前有空行方便阅读,被我精简了)。完成了我130行完成的功能,没有多余的分支,没有冗余的判断,支持所有用例的测试。性能上来说,更加的让我震惊。

大概是我这些方案的八倍左右。

我真的沉默了。

我这写的都是啥垃圾。

看这段代码,原理就是从左向右老老实实逐个查找,直到找到中位数的位置,始终保存上一位的数字和这一位的数字,剩下的都抛弃,最后判断是两个中位数取平均,还是一个中位数直接返回,其中使用了两个位运算,第一次用来计算中位数的位置,在line9,第二次在return 用来判断中位数是一个还是两个取平均,我说实话真的毫无破绽。让我看的只能用佩服来形容,这次我就不贴出来我的代码了,我要好好看看这个解决方案的运行流程,反思,反思这几个问题

1你在设计阶段没有仔细确定可行性,你在coding阶段就会付出三倍四倍甚至更多的时间去弥补这些问题,最糟的是,你设计的方案可能根本无法实现。

2有些问题不是你的方案复杂,针对的情况就多,一个健壮性强的代码,不是你后期缝缝补补得来的,而是在设计初期,方案拟定的时候就已经考虑到的,就好像一个是器官加强的人造人,一个是免疫很高的正常人。对测试用例的支持不能通过单独的设立分支来勉强维持。

3对语言和运算逻辑的缺失,还像个初学者一样傻傻的使用math函数去向上向下取整,不停地加减,在这个算法里根本看不到,位运算早就接触过,也知道他的运算速度是很快的,因为符合计算机的计算方式,但从没在时机开发和生产环境使用过,也是一个没有追求代码性能和质量的体现。

综上 这第一道hard难度的题算是告一段落了,但我从中要反思的不只是几天的胡乱cooking和极差的性能(最后这两个方案的性能都是低于90%的算法),也是在惊醒我这个领域还是有很多值得学习和思考的前辈。

最后的思考,虽然我们的解决方案在整体上大幅度低效于最优解,但在某些情况下我们的运算速度会比最优解快,比如其中一个数组的中位数命中了组合后数组的中位数时,我们将进行很少的运算。虽然我们极具创新性的思路没有在性能和简洁度上胜过最优解,但我们进行了颠覆的尝试,而最优解只在方向确定后进行了小的尝试,从这一点来看我们虽败犹荣。