4.两个排序数组的中位数（Swift版）

一、题目

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

二、解题

题目给定的两个数组都是有序数组，所以我们可以将给定的数组分为A1和A2，B1和B2，同时保证一下两个条件。
1.(A1+B1).count == (A2+B2).count 或 (A1+B1).count + 1 ==(A2+B2).count（两个数组数量相加可能是奇数，所以需要+1）；
2.保证A1+B1中的值都小于等于A2+B2中的值。
详细详解请看代码示例。

三、代码示例

    class Solution {
        func findMedianSortedArrays(_ nums1: [Int], _ nums2: [Int]) -> Double {
            var A = nums1
            var B = nums2
            if nums1.count > nums2.count {// 判断nums1和nums2的数量,将数量少的赋值给A,之后会遍历A
                A = nums2
                B = nums1
            }
            let m = A.count
            let n = B.count
            if n == 0 {// 如果n==0,由于m<n,则m也等于0,所以返回0
                return 0
            }
            
            var imin = 0
            var imax = m
            // 获取中位数所在的位置,考虑到奇数的原因,所以加1
            let half_len = (m + n + 1) / 2
            
            while imin <= imax {
                // 从A的中间位置截取A1和A2
                let i = (imin + imax) / 2
                // 中位数的位置减去i,得到B中间位置截取B1和B2,这样可以保证条件一,(A1+B1).count == (A2+B2).count
                let j = half_len - i
                // 此时A[i-1] == A1.last; A[i] == A2.first; B[j-1] == B1.last; B[j] == B2.first
                // 此时可以看出一定成立的条件A1.last<=A2.first, B1.last<=B2.first
                // 要想满足A1+B1中的值总小于等于A2+B2中的值,还需要满足A1.last <= B2.first和B1.last <= A2.first
                // 如果B1.last > A2.first, 则A中的i向右移动
                if i < m && B[j-1] > A[i] {// i<m保证A[i]存在
                    imin = i + 1
                }else if i > 0 && A[i-1] > B[j] {// 如果A1.last > B2.first,则A中的i向左移动
                    imax = i - 1
                }else{// 满足了条件2, 获取A1+B1中最大的值(max_of_left),获取A2+B2中最小的值(min_of_right)
                    
                    // 获取max_of_left
                    var max_of_left = 0
                    if i == 0 {// 如果i==0,说明A1为空,左边的最大值为B1.last
                        max_of_left = B[j-1]
                    }else if j == 0 {// t如果j==0,说明B1为空,左边的最大值为A1.last
                        max_of_left = A[i-1]
                    }else{// 取左边的最大值
                        max_of_left = max(A[i-1], B[j-1])
                    }
                    
                    if (m + n) % 2 == 1{// 如果(A+B).count是奇数,则没有max_of_left就是中位数
                        return Double(max_of_left)
                    }
                    // 获取min_of_right
                    var min_of_right = 0
                    if i == m {// 如果i==m,说明A2为空,右边的最小值为B2.first
                        min_of_right = B[j]
                    }else if j == n {// 如果j==n,说明B2为空,右边的最小值为A2.first
                        min_of_right = A[i]
                    }else{// 取右边的最小值
                        min_of_right = min(A[i], B[j])
                    }
                    // 左边的最大值和右边的最小值,组成最中间的两个数,除以2得到中位数
                    return Double((max_of_left + min_of_right)) / 2.0
                }
            }
            return 0
        }
    }

Demo地址：github