Mickey's Blog ·

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

有了之前的教训,我们这道题通过第二个方案来获取,我先简单讲解一下思路。

我们有两个数组,其实没必要从头组合出新的顺序数组就可以知道中位数的位置,那我们可以根据中位数的位置只构建一小部分,于是我们通过对比两个数组中位数的位置,将其中一个数组的中位数,挂在另一个数组上

1.png1.png

这时候我们只需要知道4在3,5之间,不需要知道2和1,3或者6和5,7的具体大小关系就可以确定4在新序列中的位置,只要我们根据这个4的位置,不断地推算靠近中位数的位置,最终就可以不用全部排序就能将中位数拿到。

但实际算法代码异常的复杂,情况非常之多,比如 这个中位数大于另一数组所有数字,或小于所有数字,而且测试用例居然还有空数组这种纯粹浪费代码量的测试数据,实在是让我非常的烦躁,我今天支持了大部分正常用例,只要不是中位数大于另一数组所有或者小于另一数组所有都能支持,但用例还是太多不能通过,准备明天将第二个方案重制。

越写到这里越觉得还是笨方法好写,但是我做这套leetcode,究其原因是对性能和效率的追求,如果只是简单的完成任务,那不能称之为一个优雅的编码者

附上方案2初步代码

1.png

1.png

1.png

1.png

需要源代码的同学可以联系我,因为js源码不太好以代码形式发布,后期可能会上传源码文件供大家下载

day1传送门:http://cheert.com/index.php/BlogDetails/index/id/128

day3传送门:http://cheert.com/index.php/BlogDetails/index/id/131