LeetCode4 寻找两个有序数组的中位数 Median of Two Sorted Arrays
题目描述
题目地址：https://leetcode-cn.com/problems/median-of-two-sorted-arrays/
题目难度：困难
给定两个大小为 m 和 n 的有序数组 nums1 和 nums2。
请你找出这两个有序数组的中位数，并且要求算法的时间复杂度为 O(log(m + n))。
你可以假设 nums1 和 nums2 不会同时为空。
示例
示例1：
nums1 = [1, 3]
nums2 = [2]
则中位数是 2.0
示例2：
nums1 = [1, 2]
nums2 = [3, 4]
则中位数是 (2 + 3)/2 = 2.5
分析
看到这道题，我想到的会是归并排序，组合成一个数组之后，取出中位数即可。
解答1：归并排序
public int[] mergeSort(int[] nums1
, int[] nums2
){
int length1
= nums1
.length
;
int length2
= nums2
.length
;
int length
= length1
+ length2
;
int[] nums3
= new int[length
];
for (int i
= 0, j
= 0, k
= 0; i
< length
; i
++) {
if (j
< length1
&& k
< length2
) {
if (nums1
[j
] < nums2
[k
]) {
nums3
[i
] = nums1
[j
++];
} else {
nums3
[i
] = nums2
[k
++];
}
} else if (j
>= length1
) {
nums3
[i
] = nums2
[k
++];
} else if (k
>= length2
) {
nums3
[i
] = nums1
[j
++];
}
}
return nums3
;
}
public double findMedianSortedArrays(int[] nums1
, int[] nums2
) {
int[] nums3
= mergeSort(nums1
, nums2
);
int len
= nums3
.length
;
int n1
= len
/ 2;
int n2
= len
% 2;
double median
;
if (n2
== 1) {
median
= nums3
[n1
];
} else {
median
= (double)(nums3
[n1
- 1] + nums3
[n1
]) / 2;
}
return median
;
}
用时：15ms,打败了64.62%的提交记录
相似题目
后续添加
总结
本题主要考察的是归并排序，在学数据结构的时候，第一章链表中有完全相同的算法，而且还有时间复杂度的提示，所以可以第一时间想到这个方法。这个算法非常经典，最开始看的时候也是看了很久才懂得。
文章哪里写的有问题欢迎指出，谢谢。
