算法-寻找两个正序数组的中位数

一、寻找两个正序数组的中位数

难度：困难

题目

给定两个大小分别为 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

提示：

0 <= nums1.length <= 1000
0 <= nums2.length <= 1000
-10^6 <= nums1[i], nums2[i] <= 10^6

思路

按照顺序定位到中位数出现的位置，本题难的是边界条件的处理。

代码

func findMedianSortedArrays(nums1 []int, nums2 []int) float64 {
	maxLen := len(nums1) + len(nums2)
	if maxLen == 0 {
		return 0.0
	}

	mIndex := maxLen / 2
	isOdd := maxLen%2 != 0

	if isOdd {
		if len(nums1) == 0 {
			return float64(nums2[mIndex])
		} else if len(nums2) == 0 {
			return float64(nums1[mIndex])
		}
	} else {
		if len(nums1) == 0 {
			return (float64(nums2[mIndex]) + float64(nums2[mIndex-1])) / 2
		} else if len(nums2) == 0 {
			return (float64(nums1[mIndex]) + float64(nums1[mIndex-1])) / 2
		}
	}

	sum := make([]int, maxLen)
	copy(sum, nums1)
	copy(sum[len(nums1):], nums2)

	sort.Ints(sum)
	if isOdd {
		return float64(sum[mIndex])
	} else {
		return (float64(sum[mIndex]) + float64(sum[mIndex-1])) / 2
	}
}

上述方法在小规模数据下，具备逻辑简单，性能没有大的印象。

大数据量，且两数组容量相差过大情况下，下列方式更为合适。

func findMedianSortedArrays(nums1 []int, nums2 []int) float64 {
    allLen := len(nums1) + len(nums2)
    if allLen == 0 {
        return 0.0
    }

	isOdd := allLen%2 != 0

	indexA, indexB := -1, -1
	lastA, lastB := -1, -1

	if len(nums1) > 0 {
		indexA = 0
		lastA = nums1[0]
	} else {
		//num1 空
		r := float64(nums2[len(nums2)/2])
		if isOdd {
			return r
		} else {
			return (float64(nums2[len(nums2)/2-1]) + r) / 2
		}
	}
	if len(nums2) > 0 {
		indexB = 0
		lastB = nums2[0]
	} else {
		r := float64(nums1[len(nums1)/2])
		if isOdd {
			return r
		} else {
			return (float64(nums1[len(nums1)/2-1]) + r) / 2
		}
	}

	mIndex := allLen / 2
	result, preResult := 0, 0
	if lastA > lastB {
		result = lastB
		indexA = -1
	} else {
		result = lastA
		indexB = -1
	}

	for indexA+indexB+1 < mIndex {
		if indexA+1 < len(nums1) {
			// nums1可以取值
			v := nums1[indexA+1]
			if v <= lastB || indexB+1 >= len(nums2) {
				indexA++
				lastA = v
				if result <= v {
					preResult = result
					result = v
				}
				if indexA == len(nums1)-1 && indexA+indexB+1 < mIndex {
					//本数组空了
					cIndex := mIndex - indexA -1
					v = nums2[cIndex]
					if result <= v {
						result = v
					}
					if !isOdd {
						preResult = nums1[indexA]
						if cIndex > 0 {
							v = nums2[cIndex-1]
							if v > preResult {
								preResult = v
							}
						}
					}
					break
				}
				continue
			}
		}
		if indexB+1 < len(nums2) {
			// nums2可以取
			v := nums2[indexB+1]
			if indexA+1 < len(nums1) && v > nums1[indexA+1] {
				indexA++
				//取A
				v = nums1[indexA]
				lastA = v
				if result <= v {
					preResult = result
					result = v
				}
				continue
			}
			indexB++
			lastB = v
			if result <= v {
				preResult = result
				result = v
			}
			if indexB == len(nums2)-1 && indexA+indexB+1 < mIndex {
				//本数组空了
				cIndex := mIndex - indexB - 1
				v = nums1[cIndex]
				if result <= v {
					result = v
				}
				if !isOdd {
					preResult = nums2[indexB]
					if cIndex > 0 {
						v = nums1[cIndex-1]
						if v > preResult {
							preResult = v
						}
					}
				}
				break
			}
			continue
		}
		break
	}
	if isOdd {
		return float64(result)
	}
	return (float64(preResult) + float64(result)) / 2
}

第二种方式实现看起来很复杂，存在思路不清楚的问题，后续有时间在优化。