LeetCode-4

 

概述

作为复杂题的第一题(Median of Two Sorted Arrays),在时间复杂度为O(log (m+n))

mn均为数组长度)的要求之下,求两个已排序数组的中位数。

分析

首先中位数的定义可以在 WikiPedia 上了解到。在已排序的前提下,即奇数元素个数的数组,为中间值;偶数元素个数的数组则为中间二值的算数平均数。

那么两个序列求中位数,可以考虑先将二者合并排序之后,进行中位数的求值。

考虑到两数组已经排序,那么我们所需要做的就是进行一次归并排序。

归并排序作为一个相当稳定的排序方式,在时间复杂度上能够满足需求。

考虑到虽然数组是排序数组,但是并没有说明是升序或是降序,无妨,如果是降序,那么将下标从尾部开始即可,但是个人测试,应该没有出现这类 case 。

解法

发表评论

电子邮件地址不会被公开。 必填项已用*标注

*

您可以使用这些HTML标签和属性: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code class="" title="" data-url=""> <del datetime=""> <em> <i> <q cite=""> <strike> <strong> <pre class="" title="" data-url=""> <span class="" title="" data-url="">

This site uses Akismet to reduce spam. Learn how your comment data is processed.