LeetCode 4寻找两个正序数组的中位数

解法一

暴力，将两个数组一一比较存到一个新的一维数组中，并保持有序，之后按照奇数偶数进行返回。

class Solution { public double findMedianSortedArrays(int[] nums1, int[] nums2) { int []num = new int[nums1.length+nums2.length]; int l1 = nums1.length; int l2 = nums2.length; int i = 0,j=0,k=0; while(i<l1&&j<l2){ if(nums1[i]<=nums2[j]){ num[k]=nums1[i]; i++; k++; } else{ num[k]=nums2[j]; j++; k++; } } while(i < l1){ num[k]=nums1[i]; i++; k++; } while(j < l2){ num[k]=nums2[j]; j++; k++; } int ll = num.length; if(ll%2!=0){ int t = ll/2; return num[t]; } return (num[ll/2]+num[ll/2-1])/2.0; } }

解法二

二分法 时间复杂度log(m+n)

class Solution { public double findMedianSortedArrays(int[] nums1, int[] nums2) { int l1 = nums1.length; int l2 = nums2.length; int left = (l1+l2+1)/2; int right = (l1+l2+2)/2; //奇数偶数统一处理，返回两数之和的平均数，奇数时两个数是相同的 return (getKth(nums1,0,l1-1,nums2,0,l2-1,left) +getKth(nums1,0,l1-1,nums2,0,l2-1,right))/2.0; } public int getKth(int []nums1,int start1,int end1, int []nums2,int start2,int end2,int k){ int len1 = end1 - start1 + 1; int len2 = end2 - start2 + 1; //判断有一个数组为空的情况直接返回 if(len1 == 0){ return nums2[start2 + k-1]; } if(len2 == 0){ return nums1[start1 + k-1]; } if(k == 1){//返回第一小的数，就比较两个数组起始位置的大小 return Math.min(nums1[start1],nums2[start2]); } int i = start1 + Math.min(len1,k/2) - 1; int j = start2 + Math.min(len2,k/2) - 1; if(nums1[i]<nums2[j]){//判断舍弃两个数组的哪一部分 //如果A[K/2]<B[K/2]那么在A[K/2]前的数都不可能是第k小的数 return getKth(nums1,i+1,end1,nums2,start2,end2,k-(i-start1+1)); } else{ return getKth(nums1,start1,end1,nums2,j+1,end2,k-(j-start2+1)); } } }