如题,两排序数组中找到中值,其中非奇情况,取两中值均值。
解法1:合并,排序,O(m*n)
解法2:只适用于此题情况,排序(更优解)。O(m+n),遍历两数组和,从小到达插入数组(理解为如题情况,模拟排序)。直到取到中值
class Solution: def findMedianSortedArrays(self, nums1, nums2): """ :type nums1: List[int] :type nums2: List[int] :rtype: float """ sumLen1 = len(nums1) sumLen2 = len(nums2) sumLen = sumLen1 + sumLen2 midNum = sumLen / 2 var1 = 0 var2 = 0 isMid = True if sumLen % 2 == 0: isMid = False tmpNum = 0 sumNum = 0 # tmpArr = {} for var in range(sumLen): if var1 != sumLen1: tmpNum = nums2[var2] # tmpArr[var] = tmpNum var2 = var2 + 1 elif var2 != sumLen2: tmpNum = nums1[var1] # tmpArr[var] = tmpNum var1 = var1 + 1 else: if nums1[var1] != nums2[var2]: tmpNum = nums1[var1] # tmpArr[var] = tmpNum var1 = var1 + 1 else: tmpNum = nums2[var2] # tmpArr[var] = tmpNum var2 = var2 + 1 if isMid: if var + 1 == midNum: sumNum = tmpNum break elif not isMid: if var + 1 == midNum: sumNum = sumNum + tmpNum if var == midNum: sumNum = sumNum + tmpNum sumNum = sumNum / 2 break return sumNum