---

Median of Two Sorted Arrays

题目描述

  给出两个有序的整数数组，需要求这两个数组合并后的中位数。如输入nums1 = [1, 3]，nums2 = [2]需要输出2.0。

题目解题思路

  最开始想法，感觉至少要排个序，时间复杂度至少需要$O(n\log{n})$O(nlogn)。后面看了题解，其实可以利用中位数的性质，即中位数左边数和右边的数一样多。那么可以假设两个数组合并后有两个中位数，一个中位数在sums1，一个中位数在sums2。sum1的中位数在第i个数和第i+1个数的中间，sums2的中位数在第j个和第j+1个数中间，那么i+j=(m+n)/2，并且要保证sums1[i-1] <= sums2[j] && sums2[j-1] <= sums1[i]即可。特殊情况下也可以一般化，比如是奇数的话，中位数只有一个那么则一定有一个数组元素全部在中位数左边或者右边。

代码

func findMedianSortedArrays(nums1 []int, nums2 []int) float64 {
    m := len(nums1)
    n := len(nums2)
    if m > n { //保证后续index2为正数
        return findMedianSortedArrays(nums2, nums1)
    }
    if m == 0 { //去除最特殊情况，某个数组为空
        m = n >> 1
        if n & 1 == 1{
            return float64(nums2[m])
        }
        return float64(nums2[m-1]+nums2[m])/2.0
    }
    
    var l, r, mid int
    var maxLeft, minRight int
    var index1, index2 int
    l, r, mid = 0, m, (n+m+1) >> 1
    for l <= r {
        index1 = (l+r) >> 1
        index2 = mid - index1
        
        if index1 < m && nums2[index2-1] > nums1[index1] { /////sums2左边大于sums1右边，则说明index1在左边，应该右移
            l = index1 + 1
        }else if index1 > 0 && nums1[index1-1] > nums2[index2] { /////说明sums1左边大于sums2右边，index1应该往左移
            r = index1 - 1
        }else { /////说明条件已经满足
            if index1 == 0 { /////说明数组1的元素都在中位数右边，那么应该中位数在sum2数组中，但是要考虑是一个还是两个的情况，所以用两个变量,这里先只考虑左边的中位数
                maxLeft = nums2[index2-1]
            }else if index2 == 0 {///数组2元素都在中位数右边，中位数在sum1数组中
                maxLeft = nums1[index1-1]
            }else { /////剩下的情况，则找出左边最大的那个数 才是中位数
                maxLeft = max(nums1[index1-1], nums2[index2-1]) ////左边的要全小于，所以要先最大的
            }
            
            if index1 == m { //数组1元素都在中位数左边
                minRight = nums2[index2]
            }else if index2 == n {
                minRight = nums1[index1]
            }else {
                minRight = min(nums2[index2], nums1[index1]) //右边的要全大于，所以要选最小的
            }
            
            if (n+m) & 1 == 1{ ////奇数个
                return float64(maxLeft)
            }
            return float64(maxLeft+minRight)/2.0
        }
    }
    return 0.0
}

func max(i, j int)int{
    if i > j {
        return i
    }
    return j
}

func min(i, j int)int{
    if i > j {
        return j
    }
    return i
}