这道题最初是Sure讲给我的,后来在LeetCode碰到了,好题。

方法一:借助插入排序的思想,复杂度O(m + n)。用两个指针分别指向两个数组的首地址(用两个代表数组下标的变量,不妨设idx_a,idx_b,初始为0),然后比较A[idx_a]和B[idx_b]的大小,值小的下标向后移动一个位置(idx_a++或idx_b++),然后继续比较,直到当前idx_a或者idx_b位置恰好处在两个数组的中间位置,记录下当前位置的值就是结果。至于m+n的奇偶情况对应处理就好。

方法二:不难想到用二分做一个简单的优化,复杂度max(O(mlogn),O(nlogm))。枚举其中一个数组的元素,二分得到该元素在第二个数组中的位置,然后根据该元素在两个数组中的位置判断是否为中值。想法应该很好理解,程序写起来需要处理的细节却很多。

方法三:既然可以max(O(mlogn),O(nlogm))得到某个元素在两个数组中的“综合排名”,而现在只需要中间排名的值,那么是否可以根据当前计算得到的排名和中间排名作比较从而对第一个数组中元素的位置也二分着进行调整。此时复杂度可以优化到O(lognlogm),已经是一个不错的方法了。

方法四:同样是二分查找,但是换一个角度考虑,如果能够把这两个数组当成一个整体进行考虑,那么变化的无非是查找元素的总个数,复杂度还是log级别。如果能够想办法解决查找两个有序数组第k大元素这样一个问题,本问题就迎刃而解了。下面这段程序参考过别人的思想,非常优秀漂亮的解法。