本文共 1464 字，大约阅读时间需要 4 分钟。

4.寻找两个正序数组的中位数

题目描述： 题解一： 合并两个数组，找其中位数。 1.合并两个数组为数组nums。 2.将数组nums从小到大排序。 3.计算数组nums的长度n即元素有多少。 (1)如果n为偶数,则中文数为数组nums中第(n/2)个位置元素与第[(n/2)+1]个位置元素之和的一半。 (2)如果n为奇数,则中文数为数组nums中第[(n+1)/2]个位置元素。 时间复杂度：O(m+n) 空间复杂度: O(m+nm+n)

class Solution(object):     def findMedianSortedArrays(self,nums1,nums2):        """        :type nums1: List[int]        :type nums2: List[int]        :rtype: float        """        nums=sorted(nums1+nums2)        n=len(nums)        if h%2!=0:            k=int((n+1)/2)            answer=nums[k-1]        else:            k=int((n)/2)            answer=(nums[k+1]+nums[k])/2        print(answer)

题解二：

双指针移动法,找到中位数所在的位置。

理解 1.需要遍历的次数count： 用 length表示合并后数组的长度，如果length是奇数，我们需要知道第 （length+1）/2 个数就可以了，如果遍历的话需要遍历 int(length/2 ) + 1 次。如果是偶数，我们需要知道第 length/2和 (length/2+1)个数，也是需要遍历 (length/2+1 )次。所以遍历的话，奇数和偶数都是 int(length/2)+1 次。 2.记录输出结果： 奇数需要最后一次遍历的结果就可以了，偶数需要最后一次和上一次遍历的结果。所以我们用两个变量 left 和 right，right 保存当前循环的结果，在每次循环前将 right 的值赋给 left。这样在最后一次循环的时候，left 将得到 right 的值，也就是上一次循环的结果，接下来 right 更新为最后一次的结果。 3.指针移动情况： 指针p,r分别指向A数组，B数组。 如果 p还没有到A数组最后的位置并且此时 A 位置的数字小于 B 位置的数组，那么p就可以后移了;否则，r后移。 python：

def findMedianSortedArrays(A, B):    m=len(A)    n=len(B)    length=m+n    p=0    r=0#初始化指针p,r    left=-1    right=-1#left表示当前循环的前一值，right表示当前循环的值    count=int(length/2)+1    for i in range(count):        left=right        if p

时间复杂度：遍历int(m+n/2)+1次，故时间复杂度为O（m+n)

空间复杂度： 我们申请了常数个变量，也就是 m，n，length，left，right，p，r，i。 总共 8 个变量，所以空间复杂度是 O(1）

题解三：