给定两个大小分别为 m 和 n 的正序（从小到大）数组 nums1 和 nums2。请你找出并返回这两个正序数组的 中位数 。
算法的时间复杂度应该为 O(log (m+n)) 。

解题思路

看到这题后的第一想法就是利用两个指针，再用归并成一个数组在取其中位数。

  1. const findMedianSortedArrays = function(nums1, nums2) {
  2.     let index1 = 0
  3.     let index2 = 0
  4.     let result = []
  5.     while(index1<nums1.length && index2<nums2.length){
  6.         if(nums1[index1]>nums2[index2]){
  7.           result.push(nums2[index2])
  8.         index2++
  9.       }else{
  10.           result.push(nums1[index1])
  11.         index1++
  12.       }
  13.     }
  14.       if(index1===nums1.length){
  15.         result = result.concat(nums2.slice(index2))
  16.     }else{
  17.         result = result.concat(nums1.slice(index1))
  18.     }
  19.       let length = result.length
  20.     if(length/2===parseInt(length/2)){
  21.         return (result[length/2]+result[length/2-1])/2
  22.     }else{
  23.         return result[parseInt(length/2)]
  24.     }
  26. }

Go

go版本，没有什么大的区别。go中的数组不能push只能预先分配大小，然后根据索引设置值。

  1. func findMedianSortedArrays(nums1 []int, nums2 []int) float64 {
  2.     index1,index2,k := 0,0,0
  3.     m,n := len(nums1),len(nums2)
  4.     result := make([]int,m+n)
  5.     var res float64
  6.     for ;k<m+n;k++ {
  7.         if index1 < m && index2 < n {
  8.             if nums1[index1]>nums2[index2] {
  9.                 result[k] = nums2[index2]
  10.                 index2++
  11.             }else{
  12.                 result[k] = nums1[index1]
  13.                 index1++
  14.             }
  15.         }else if index1<m {
  16.             result[k] = nums1[index1]
  17.             index1++
  18.         }else{
  19.             result[k] = nums2[index2]
  20.             index2++
  21.         }
  22.     }
  24.     if len(result)%2==0 {
  25.         res = float64(result[len(result)/2] + result[len(result)/2-1])/2
  26.     }else{
  27.         res = float64(result[len(result)/2])
  28.     }
  29.     return res
  30. }

Rust

rust版本。

impl Solution {
    pub fn find_median_sorted_arrays(nums1: Vec<i32>, nums2: Vec<i32>) -> f64 {
        let mut index1 = 0;
        let mut index2 = 0;
        let mut m = nums1.len();
        let mut n = nums2.len();
        let mut result = vec![];

        while index1 < m && index2 < n {
            if nums1[index1] > nums2[index2] {
                result.push(nums2[index2]);
                index2 += 1;
            } else {
                result.push(nums1[index1]);
                index1 += 1;
            }
        }

        if index1 == m {
            while index2 < n {
                result.push(nums2[index2]);
                index2 += 1;
            }
        } else {
            while index1 < m {
                result.push(nums1[index1]);
                index1 += 1;
            }
        }
        let length = result.len();
        if length % 2 == 0 {
            (result[(length / 2)] as f64 + result[(length / 2) - 1] as f64) / 2 as f64
        } else {
            result[(length / 2)] as f64
        }
    }
}

附加题

题目的条件是使时间复杂度降到O(log(m+n))，所以这才让这道题变成一道困难题。根据这个复杂度我们应该使用二分查找的方法。
二分查找的思路是这样的
image.pngimage.png
有两种情况，一种是两个数组的元素数量是奇数时，我们就会取左侧最大数。另一种偶数时，我们取左侧最大右侧最小值的平均数。这条分割线的规则就是 左右两边的元素的数量要相等或者左边多一个，并且左边的数要全部小于右边的数。
image.png
上面四种是特殊情况有的时候线的两端是没有数字的，所以在这种情况要对最后取数的时候进行判断，如果遇到没有数的情况就要对其赋值为最大值和最小值
Number.MIN_SAFE_INTEGER以及Number.MAX_SAFE_INTEGER

const findMedianSortedArrays = function (num1, num2) {
    if (num1.length > num2.length) {
        let temp = num1
        num1 = num2
        num2 = temp
    }
    let m = num1.length
    let n = num2.length
    //分割线左边的所有元素需要满足的个数 m + (n - m + 1)/2
    let totalLeft = parseInt((m + n + 1) / 2)

    //在num1的区间[0, m]里查找恰当的分割线
    //使得 num1[i-1]<=num2[j] && num1[j-1]<=num2[i]
    let left = 0
    let right = m
    while (left < right) {
        let i = left + parseInt((right - left + 1) / 2)
        let j = totalLeft - i
        if (num1[i - 1] > num2[j]) { // 违反上面的条件 所以这样写
              //下一轮搜索区间 [left, i-1]
            right = i - 1
        } else {
              //下一轮搜素区间 [i, right]
            left = i
        }
    }
    let i = left
    let j = totalLeft - i

    let nums1LeftMax = i === 0 ? Number.MIN_SAFE_INTEGER : num1[i - 1]
    let nums1RightMin = i === m ? Number.MAX_SAFE_INTEGER : num1[i]
    let nums2LeftMax = j === 0 ? Number.MIN_SAFE_INTEGER : num2[j - 1]
    let nums2RightMin = j === n ? Number.MAX_SAFE_INTEGER : num2[j]
    if ((m + n) % 2 === 1) {
        console.log(nums1LeftMax, nums2LeftMax)
        return Math.max(nums1LeftMax, nums2LeftMax)
    } else {
        return (Math.max(nums1LeftMax, nums2LeftMax) + Math.min(nums1RightMin, nums2RightMin)) / 2
    }
}