@Yano 2018-11-24T07:10:26.000000Z 字数 1791 阅读 1003

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

# 代码实现

1. public double findMedianSortedArrays(int[] nums1, int[] nums2) {
2. if (nums1.length > nums2.length) {
3. return findMedianSortedArrays(nums2, nums1);
4. }
5. int x = nums1.length, y = nums2.length;
6. int low = 0, high = x;
7. while (low <= high) {
8. int partitionX = (low + high) / 2;
9. int partitionY = (x + y + 1) / 2 - partitionX;
10. int maxLeftX = (partitionX == 0) ? Integer.MIN_VALUE : nums1[partitionX - 1];
11. int maxLeftY = (partitionY == 0) ? Integer.MIN_VALUE : nums2[partitionY - 1];
12. int minRightX = (partitionX == x) ? Integer.MAX_VALUE : nums1[partitionX];
13. int minRightY = (partitionY == y) ? Integer.MAX_VALUE : nums2[partitionY];
14. if (maxLeftX <= minRightY && maxLeftY <= minRightX) {
15. if ((x + y) % 2 == 0) {
16. return (Math.max(maxLeftX, maxLeftY) + Math.min(minRightX, minRightY)) / 2.0;
17. } else {
18. return Math.max(maxLeftX, maxLeftY);
19. }
20. } else if (minRightX < maxLeftY) {
21. low = partitionX + 1;
22. } else {
23. high = partitionX - 1;
24. }
25. }
26. throw new RuntimeException();
27. }

# 总结

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

• 私有
• 公开
• 删除