给定两个大小分别为 m 和 n 的正序（从小到大）数组 nums1 和 nums2。请你找出并返回这两个正序数组的 中位数 。
算法的时间复杂度应该为 O(log (m+n)) 。
示例 1：
输入：nums1 = [1,3], nums2 = [2]
输出：2.00000
解释：合并数组 = [1,2,3] ，中位数 2
示例 2：
输入：nums1 = [1,2], nums2 = [3,4]
输出：2.50000
解释：合并数组 = [1,2,3,4] ，中位数 (2 + 3) / 2 = 2.5
提示：
nums1.length == m
nums2.length == n
0 <= m <= 1000
0 <= n <= 1000
1 <= m + n <= 2000
-106 <= nums1[i], nums2[i] <= 106
解题：
java:
class Solution { public double findMedianSortedArrays(int[] nums1, int[] nums2) { int[] arr3=new int[nums1.length+ nums2.length]; int p1=0,p2=0,p=0; while (p1< nums1.length&&p2< nums2.length){ int i1 = nums1[p1]; int i2 = nums2[p2]; if (i1<=i2){ arr3[p++]=i1; p1++; }else { arr3[p++]=i2; p2++; } if (p>arr3.length/2){ if (arr3.length%2==0){ return ((double) (arr3[arr3.length/2-1]+arr3[arr3.length/2]))/2; }else { return arr3[arr3.length/2]; } } } if (p1!= nums1.length){ while (p1< nums1.length){ arr3[p++]= nums1[p1++]; if (p>arr3.length/2){ if (arr3.length%2==0){ return ((double) (arr3[arr3.length/2-1]+arr3[arr3.length/2]))/2; }else { return arr3[arr3.length/2]; } } } } if (p2!= nums2.length){ while (p2< nums2.length){ arr3[p++]= nums2[p2++]; if (p>arr3.length/2){ if (arr3.length%2==0){ return ((double) (arr3[arr3.length/2-1]+arr3[arr3.length/2]))/2; }else { return arr3[arr3.length/2]; } } } } if (arr3.length%2==0){ return ((double) (arr3[arr3.length/2-1]+arr3[arr3.length/2]))/2; }else { return arr3[arr3.length/2]; } }}javascript:
解题思路
题目要求时间复杂度为O(log (m + n)),一般带有log就要想到二分法
求一个有序数组的中位数，有两种情况:
数组长度为奇数，中位数是数组的中间数字: arr[Math.floor((arr.length + 1) / 2) - 1]
数组长度为偶数，中位数是数组的中间两个数字和除以2: (arr[Math.floor((arr.length + 1) / 2) - 1] + arr[Math.floor((arr.length + 2) / 2] - 1) / 2
上面【】中减一的原因是数组下标从0开始
设i = Math.floor((arr.length + 1) / 2)，j = Math.floor((arr.length + 2) / 2
可以将找中位数转化成找有序数组第i小和第j小的数字
设p = Math.floor(k / 2)
在两个正序数组中找第k小的数字步骤:
比较arr1[p - 1]和arr2[p - 1],假设前者小
因为两个数组都是正序，所以arr1中下标在[0, p - 1]范围的都不可能是第k小的数，可以排除，arr1剩下下标[p, arr1.length - 1]
步骤2的[0, p - 1]范围都是比第k小的数字还要小的数字，所以只要在剩下两个数组中找到第k - (p - 1 - 0 + 1)小的数字,新一轮的k = k - (p - 1 - 0 + 1)
重复上面的步骤，直到k === 1，这时候比较两个剩下的数组中第一个数字大小，取最小的就是结果
这个过程中还要考虑特殊情况:
其中一个数组的长度小于p:直接取最后一个数字
其中一个数组长度等于0: 从另一个数组中取第k小的数字
arr1[p - 1] === arr2[p - 1]: 随便删去其中一个数组的前p个数(代码中将它放在else中处理)
代码
/** * @param {number[]} nums1 * @param {number[]} nums2 * @return {number} */var findMedianSortedArrays = function(nums1, nums2) { let len1 = nums1.length; let len2 = nums2.length; let left = Math.floor((len1 + len2 + 1) / 2); let right = Math.floor((len1 + len2 + 2) / 2); return (findkth(nums1, 0, len1 - 1, nums2, 0, len2 - 1, left) + findkth(nums1, 0 , len1 - 1, nums2, 0, len2 - 1, right)) / 2;};
function findkth(arr1, start1, end1, arr2, start2, end2, k) { let n = end1 - start1 + 1; let m = end2 - start2 + 1; if(n > m) return findkth(arr2, start2, end2, arr1, start1, end1, k); if(n === 0) return arr2[start2 + k - 1]; if(k === 1) return Math.min(arr1[start1], arr2[start2]); let i = start1 + Math.min(n, Math.floor(k / 2)) - 1; let j = start2 + Math.min(m, Math.floor(k / 2)) - 1; if(arr1[i] > arr2[j]) { return findkth(arr1, start1, end1, arr2, j + 1, end2, k - (j - start2 + 1)); } else { return findkth(arr1, i + 1, end1, arr2, start2, end2, k - (i - start1 + 1)); }}