给定两个大小为 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
思路:
简单粗暴,先将两个数组合并,两个有序数组的合并也是归并排序中的一部分。然后根据奇数,还是偶数,返回中位数。
package find_median_sorted_arrays;
public class Solution {
public int[] merge(int[] nums1, int[] nums2){
int len1=nums1.length;
int len2=nums2.length;
int len3=len1+len2;
int[] nums3=new int[len3];
int i=0,j=0,k=0;
while(i<len1&&j<len2){
int num1=nums1[i];
int num2=nums2[j];
if (num1>num2){
nums3[k++]=num2;
j++;
}else{
nums3[k++]=num1;
i++;
}
}
while(i<len1){
nums3[k+