@Yano 2018-11-24T15:10:26.000000Z 字数 1791 阅读 2066

# LeetCode 004 Median of Two Sorted Arrays 详细分析

LeetCode

# 题目描述

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.

Example 1:

nums1 = [1, 3]
nums2 = [2]


The median is 2.0
Example 2:

nums1 = [1, 2]
nums2 = [3, 4]


The median is (2 + 3)/2 = 2.5

# 题目分析

## 算法分析

len(X1) + len(Y1) == len(X2) + len(Y2)

len(X1) + len(Y1) == len(X2) + len(Y2) + 1


# 代码实现

public double findMedianSortedArrays(int[] nums1, int[] nums2) {    if (nums1.length > nums2.length) {        return findMedianSortedArrays(nums2, nums1);    }    int x = nums1.length, y = nums2.length;    int low = 0, high = x;    while (low <= high) {        int partitionX = (low + high) / 2;        int partitionY = (x + y + 1) / 2 - partitionX;        int maxLeftX = (partitionX == 0) ? Integer.MIN_VALUE : nums1[partitionX - 1];        int maxLeftY = (partitionY == 0) ? Integer.MIN_VALUE : nums2[partitionY - 1];        int minRightX = (partitionX == x) ? Integer.MAX_VALUE : nums1[partitionX];        int minRightY = (partitionY == y) ? Integer.MAX_VALUE : nums2[partitionY];        if (maxLeftX <= minRightY && maxLeftY <= minRightX) {            if ((x + y) % 2 == 0) {                return (Math.max(maxLeftX, maxLeftY) + Math.min(minRightX, minRightY)) / 2.0;            } else {                return Math.max(maxLeftX, maxLeftY);            }        } else if (minRightX < maxLeftY) {            low = partitionX + 1;        } else {            high = partitionX - 1;        }    }    throw new RuntimeException();}

# 总结

1. 数组长度的奇偶
2. 移动过程中，某个数组被切割后可能为空

• 私有
• 公开
• 删除