LeetCode算法题-4. 寻找两个有序数组的中位数（Swif

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/median-of-two-sorted-arrays

题目

给定两个大小为 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

两个数组的数，合起来后，算中间的数。

方法

func findMedianSortedArrays(_ nums1: [Int], _ nums2: [Int]) -> Double {
                
        //假设两个数组分别是A和B。且A.count <= B.count。
        let numsA = (nums1.count <= nums2.count) ? nums1 : nums2
        let numsB = (numsA == nums1) ? nums2 : nums1
        
        //两个数组个数m,n。   m<n
        let m = numsA.count
        let n = numsB.count
        
        //中位数相当于，将数组分割成相等数量的两个数组。
        //即将A和B两个数组合成一个数组后，应当保证中位数左边的数组个数 = 中位数右边的数组个数（有可能是(m+n)/2 + 1） = (m+n)/2
        //且合成后，也需要是一个有序数组。假设，A数组有i个在边，B数组有j个在左边。则要保证A[i-1] <= B[j] && B[j-1] <= A[i]
        //满足上述之后。那么左边最大的数leftMax = max(A[i-1],B[j-1]).右边最小的rightMin = min(A[i],B[j])
        //那么中位数result就可以知道了，如果(m+n)%2==0.result = (leftMax +rightMin)/2.0.
        //                         否则，result = rightMin。
        
        //左边的个数。
        let sideNum = (m+n)/2
        
        //i的最小值和最大值。
        var iMin = 0
        var iMax = m
        
        //二分法开始找左边的i。
        while iMin <= iMax {
            
            //A数组左边个数。
            let i = (iMin + iMax) / 2
            //B数组左边个数。
            let j = sideNum - i
            
            if (i > iMin && numsA[i-1] > numsB[j]) {
                //如果左边A最后一个 > 右边B第一个
                iMax = i-1
            }else if (i < iMax && numsB[j - 1] > numsA[i]) {
                //如果左边B最后一个 < 右边A第一个
                iMin = i+1
            }else {
                
                var rightMin = 0
                if i == m {
                    rightMin = numsB[j]
                }else if j == n {
                    rightMin = numsA[i]
                }else {
                    rightMin = min(numsB[j], numsA[i])
                }
                
                if (m+n) % 2 != 0 {
                    return Double(rightMin)
                }
                var leftMax = 0
                if i == 0 {
                    leftMax = numsB[j-1]
                }else if (j == 0) {
                    leftMax = numsA[i-1]
                }else {
                    leftMax = max(numsA[i-1], numsB[j-1])
                }
                return Double(leftMax + rightMin)/2.0
            }
        }
        return 0
    }