寻找两个正序数组的中位数-Leetcode04
如题：
给定两个大小为 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
代码：
/**
* 给定两个大小为 m 和 n 的正序（从小到大）数组 nums1 和 nums2。
*
* 请你找出这两个正序数组的中位数，并且要求算法的时间复杂度为 O(log(m + n))。
*
* 你可以假设 nums1 和 nums2 不会同时为空。
*/
public class Solution {
public double findMedianSortedArrays(int[] nums1, int[] nums2) {int n=nums1.length;
int m=nums2.length;
int left=(n+m+1)/2;
int right=(n+m+2)/2;
return (getKth(nums1,0,n-1,nums2,0,m-1,left)+getKth(nums1,0,n-1,nums2,0,m-1,right))*0.5;
}private 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;
//让len1的长度小于len2，这样就能保证如果有数组空了，一定是len1
if(len1>len2) {
return getKth(nums2, start2, end2, nums1, start1, end1, k);
}
if(len1==0){
return nums2[start2+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]){
return getKth(nums1,start1,end1,nums2,j+1,end2,k-(j-start2+1));
}else{
return getKth(nums1,i+1,end1,nums2,start2,end2,k-(i-start1+1));
}}/*public double findMedianSortedArrays(int[] nums1, int[] nums2) {int[] nums;
int m= nums1.length;
int n=nums2.length;
nums=new int[m+n];
if(m==0){
if(n%2==0){
return (nums2[n/2-1]+nums[n/2])/2.0;
}else{
return nums2[n/2];
}
}
if(n==0){
if(m%2==0){
return (nums1[m/2-1]+nums1[m/2])/2.0;
}else{
return nums1[m/2];
}
}int count=0;
int i=0,j=0;
while(count!=(m+n)){
//nums1数组先遍历完
if(i==m){
while(j!=n){
nums[count++]=nums1[j++];
}
break;
}
//nums2数组先遍历完
if(j==n){
while(i!=m){
nums[count++]=nums1[i++];
}
break;
}//一般情况，对两个数组进行遍历，将数组元素放到第三个数组中
if(nums1[i]思路：转自Leetcode官网有才的程序员
链接https://leetcode-cn.com/problems/median-of-two-sorted-arrays/solution/xiang-xi-tong-su-de-si-lu-fen-xi-duo-jie-fa-by-w-2/
【寻找两个正序数组的中位数-Leetcode04】来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/median-of-two-sorted-arrays
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
推荐阅读
- 如何寻找情感问答App的分析切入点
- 刘婵为何不娶关羽的女儿为妻子，而为何要娶张飞的两个女儿
- 说睡
- 寻找春天（2018.3）
- 寻找天使啦~~~
- 有人与我谈格局
- 装修公司如何寻找精准客户
- ||11|2019年9月9日
- 活的教导7:两个阶段
- 2021年第四周复盘|2021年第四周复盘 | 寻找初心，再次出发