暴力解法

思路

合并两个代码后从小到大排序，数组总数是奇数取nums[n/2]，是偶数则取(nums[n/2] + nums[n/2-1]) / 2

代码

复制
1/**
2 * @param {number[]} nums1
3 * @param {number[]} nums2
4 * @return {number}
5 */
6var findMedianSortedArrays = function(nums1, nums2) {
7    let n = nums1.length + nums2.length;
8    let nums = nums1.concat(nums2).sort((a, b) => a - b);
9    
10    let result = n % 2 == 0
11        ? (nums[n/2] + nums[n/2-1]) / 2
12        : nums[Math.floor(n/2)];
13
14    return result;
15};

复杂度

• 时间复杂度 O(NlogN)，N为两数组的长度和
• 空间复杂度 O(N)

双指针法

思路

因为两个数组有序，求中位数不需要把两个数组合并

当合并后的数组总长度len为奇数时，只要知道索引为len/2位置上的数就行了，如果数偶数，只要知道索引为len/2 - 1和len/2上的数就行，所以不管是奇数还是偶数只要遍历len/2次即可，用两个值来存遍历过程中len/2-1和len/2上的数即可

两个指针point1和point2分别指向nums1和nums2，当nums1[point1] < nums2[point2]，则point1指针移动，否则point2指针移动

代码

复制
1/**
2 * 
3 * 
4 * @param {number[]} nums1
5 * @param {number[]} nums2
6 * @return {number}
7 */
8var findMedianSortedArrays = function(nums1, nums2) {
9    let n1 = nums1.length;
10    let n2 = nums2.length;
11
12    // 两个数组总长度
13    let len = n1 + n2;
14
15    // 保存当前移动的指针的值(在nums1或nums2移动)，和上一个值
16    let preValue = -1;
17    let curValue = -1;
18
19    //  两个指针分别在nums1和nums2上移动
20    let point1 = 0;
21    let point2 = 0;
22
23    // 需要遍历len/2次，当len是奇数时，最后取curValue的值，是偶数时，最后取(preValue + curValue)/2的值
24    for (let i = 0; i <= Math.floor(len/2); i++) {
25        preValue = curValue;
26        // 需要在nums1上移动point1指针
27        if (point1 < n1 && (point2 >= n2 || nums1[point1] < nums2[point2])) {
28            curValue = nums1[point1];
29            point1++;
30        } else {
31            curValue = nums2[point2];
32            point2++;
33        }
34    }
35    
36    return len % 2 === 0 
37        ? (preValue + curValue) / 2
38        : curValue
39};

复杂度

• 时间复杂度O(n+m)，n为nums1的长度，m为nums2的长度
• 空间复杂度O(1)

二分查找

思路

对于中位数的简单分析

如果两个数组长度和为奇数，那么最终这个中位数是由一位数确定的。

如果两个数组长度和为偶数，那么最终这个中位数是由两位数取平均值确定的。

对两个数组的简单分析：

两个数组应该有一个长一点，另一个点一点(等长也不影响)。

中位数可能让两个数组都分成两部分：一部分小于中位数，一部分大于中位数。但两个部分合起来总数量应该一致。

对两数组和中位数位置分析：

我们知道两数组虽然可能等长(不影响)，但正常情况应该是一个长(m)一个短(n)。长短数组分别对应的坐标m1和n1和中位数坐标有什么关系？

无论总和奇数偶数，都满足(m1+n1)=(m+n)/2;因为两个数组都是有序的所以总共小于中位数的占一半。其中m和n是定值。也就是不管你怎么变动，这两个坐标编号总和为定值。

如何分析为定值得坐标

既然两个坐标的总和为定值，那么可不可以把其中一个当为自变量，一个看成自变量呢？

比如x+y=5你不好分析但是y=5-x，你分析x同时y就确定了。对吧？

那么选择长的那个作为变量还是短的那个作为变量呢？短的。

为啥？主要因为如果从长的当成变量咱们有些区域无法对应到短的(因为长度即使加上短的所有也到不了一半，处理起来麻烦，但是短的就可以很好避免这种情况。

所以我们就用二分去查找小的这个区间，找到最终的结果，你可能会问：什么样情况能够满足确定这条线的附近就是产生中位数的？

二分进行查找编号的时候，满足左侧都比线右侧小才行。这种情况在二分查找就是一个平衡的结果。

最后找到这个index线了。取值比较你还要有注意的地方：取左侧的时候左侧如果有index为0，取右侧的时候index为最大值。

所以在最后取值的时候，需要考虑左右侧是否有值。同时取长的那个也要比较，因为可能出现等长情况例如：1 2 3 4,和5 6 7 8这种去到临界。需要判断当然在实现过程用三目运算简化！

总结：

• 根据短的进行二分查找位置，先找到线index，说明中位数在附近产生。（奇数偶数在查找因为要除2可以通用表达式）
• 如果总个数奇数，那么就是线左侧最大的那个(两个比较或只有一个)
• 如果总个数偶数，那么就是线左侧最大的那个(两个比较或只有一个)和线右侧最小的那个(两个比较或只有一个)的值取平均，注意是double类型。
• 其他注意点，搞清index从0开始，搞清逻辑上的第几个和数组显示使用的第几个的index的区别。

代码

复制
1/**
2 * 
3 * 
4 * @param {number[]} nums1
5 * @param {number[]} nums2
6 * @return {number}
7 */
8var findMedianSortedArrays = function(nums1, nums2) {
9    // nums1长度比nums2小
10    if (nums1.length > nums2.length) {
11        [nums1, nums2] = [nums2, nums1];
12    }
13
14    let m = nums1.length;
15    let n = nums2.length;
16    // 在0～m中查找
17    let left = 0;
18    let right = m;
19
20    // median1：前一部分的最大值
21    // median2：后一部分的最小值
22    let median1 = 0;
23    let median2 = 0;
24
25    while(left <= right) {
26        // 前一部分包含 nums1[0 .. i-1] 和 nums2[0 .. j-1]
27        // 后一部分包含 nums1[i .. m-1] 和 nums2[j .. n-1]
28        const i = left + Math.floor((right - left) / 2);
29        const j = Math.floor((m + n + 1) / 2) - i;
30        
31        const maxLeft1 = i === 0 ? -Infinity : nums1[i - 1];
32        const minRight1 = i === m ? Infinity : nums1[i];
33
34        const maxLeft2 = j === 0 ? -Infinity : nums2[j - 1];
35        const minRight2 = j === n ? Infinity : nums2[j];
36
37        if (maxLeft1 <= minRight2) {
38            median1 = Math.max(maxLeft1, maxLeft2);
39            median2 = Math.min(minRight1, minRight2);
40            left = i + 1;
41        } else{
42            right = i - 1;
43        }
44    }
45    return (m + n) % 2 == 0 ? (median1 + median2) / 2 : median1;
46};

复杂度

• 时间复杂度O(log(min(m, n)))，n为nums1的长度，m为nums2的长度
• 空间复杂度O(1)