【数组 &双指针】Leecode-4. 寻找两个正序数组的中位数

【题目】

给定两个大小分别为 m 和 n 的正序（从小到大）数组 nums1 和 nums2。请你找出并返回这两个正序数组的 中位数 。

算法的时间复杂度应该为 O(log (m+n)) 。

示例 1：

输入：nums1 = [1,3], nums2 = [2]
输出：2.00000
解释：合并数组 = [1,2,3] ，中位数 2

示例 2：

输入：nums1 = [1,2], nums2 = [3,4]
输出：2.50000
解释：合并数组 = [1,2,3,4] ，中位数 (2 + 3) / 2 = 2.5

【题解】

    题解1：

• 思路

         将两个数组合并并排序，取中位数，快但不符合复杂度要求

• 复杂度

         时间复杂度：O(1)，空间复杂度：O(1)

• 代码

class Solution:
    def findMedianSortedArrays(self, nums1: List[int], nums2: List[int]) -> float:
      nums1.extend(nums2).sort()
      n = len(nums1)
      return  (nums1[int(n/2)]+nums1[int(n/2)-1])/2 if n%2==0 else nums1[int(n/2)]

    题解2：

• 思路：

        双指针，需要先进行排序

• 复杂度

         时间复杂度：$O(nlogn)$，空间复杂度：O(n)

• 代码

class Solution:
    def findMedianSortedArrays(self, nums1: List[int], nums2: List[int]) -> float:
      m = len(nums1)
      n = len(nums2)
      mid = (m+n)/2
      pre1 = 0
      pre2 = 0
      ret = []
      while len(ret) < mid+1:
          if pre1>m-1:
              ret.append(nums2[pre2])
          elif pre2>n-1:
              ret.append(nums1[pre1])
          elif nums1[pre1] < nums2[pre2]:
              ret.append(nums1[pre1])
              pre1 += 1
          else:
              ret.append(nums2[pre2])
              pre2 +=1
      if (m+n)%2 == 0:
          return (ret[-1]+ret[-2])/2
      else:
          return ret[-2]