leetcode刷题day03-4. Median of Two Sorted Arrays

东阳的学习记录，坚持就是胜利！

文章目录

题目：我的解法：分治法算法思想如下算法的具体步骤python实现

题目：

There are two sorted arrays nums1 and nums2 of size m and n respectively. Find the median of the two sorted arrays. The overall run time complexity should be O(log (m+n)). You may assume nums1 and nums2 cannot be both empty. leetcode： Median of Two Sorted Arrays

我的解法：

时间复杂度：O(m + n)空间复杂度：O(1) def findMedianSortedArrays(nums1, nums2) -> float: l1 = len(nums1) nums1.extend(nums2) l = len(nums1) merge(nums1, 0, l1 - 1, l - 1) if l % 2 == 0: return (nums1[l // 2 - 1] + nums1[l // 2]) / 2 else: return nums1[l // 2] def merge(alist, low, mid, high): """ 表alist的两段各自有序，将他们合并成个一个有序表 """ temp = [0 for _ in range(len(alist))] for k in range(low, high + 1): # 将alist中所有元素复制到temp中 temp[k] = alist[k] i, j = low, mid + 1 k = i count = 0 while i <= mid and j <= high: if temp[i] <= temp[j]: # 比较temp的左右两段元素 # 将较小值复制到alist中 alist[k] = temp[i] i += 1 else: alist[k] = temp[j] j += 1 k += 1 while i <= mid: # 若第一个表未检测完，复制 alist[k] = temp[i] k += 1 i += 1 while j <= high: # 若第二个表未检测完，复制 alist[k] = alist[j] k += 1 j += 1

分治法

时间复杂度：O(log(m+n))

采用二分查找的思想。

算法思想如下

假设我们的中位数是在A[i]，可以知道中位数左边的数都小于它，右边的数都大于它，并且各占一半（假设数组长度和是偶数）这就意味着A数组从A[0]到A[i-1]，B数组从B[0]到B[j-1]都要小于A[i]

i和j的关系，i代表A中小于中位数的元素个数，j代表B中小于中位数的元素个数，那么有： $i+j=（m+n)/2$。即 $j=(m+n)/2-i$

我们的任务就是找到满足条件的$i$，易知 $i=(imin+imax)/2$

算法的具体步骤

初始化i，i=(imin+imax)/2如果$A[i]>A[j-1]andA[i-1]<A[j]$，则$A[i]$即为中位数，否则进入第三步调整i的位置如果A[i] < A[j-1]，增大左边界imin；如果A[i-1]>A[j]，减小右边界。找到符合条件的i后，输出结果（这里好麻烦）

注意边界的处理

python实现

class Solution: def findMedianSortedArrays(self, nums1: List[int], nums2: List[int]) -> float: lenA=len(nums1) lenB=len(nums2) if lenA>lenB: # 将较长的数组放在nums1， 保证中位数索引小于Len(A) nums1,nums2,lenA,lenB=nums2,nums1,lenB,lenA imin,imax=0,lenA, # left_position mid=int((lenA+lenB)/2) while imin<=imax: i=int((imin+imax)/2) j=mid-i if i<lenA and nums1[i]<nums2[j-1]: # 如果 nums1[] < nums2[], 调整A左边界 imin=i+1 elif 0<i and nums1[i-1]>nums2[j]: # 调整右边界 imax=i-1 else: break # 找到了符合条件的i if lenA == 0: if (lenA + lenB) % 2 == 0: return (nums2[int(lenB / 2)] + nums2[int(lenB / 2) - 1]) / 2 else: return nums2[int(lenB / 2)] # 找到了i, j 的值 min_right, max_left= 0, 0 # 确定左边的最大值 if i==0: max_left=nums2[j-1] elif j==0: max_left=nums1[i-1] else: max_left = max(nums1[i-1], nums2[j-1]) # 确定右边的最小值 if i == lenA: min_right = nums2[j] # 此时A中所有元素都小于中位数 elif j == lenB: min_right = nums1[i] # 此时B中所有元素都小于中位数 else: min_right = min(nums1[i], nums2[j]) if (lenA + lenB) % 2 == 0: return (max_left + min_right) / 2 else: return min_right