7、Median of Two Sorted Arrays（Hard）

Problem Description

There are two sorted arrays nums1 and nums2 of size m and n respectively. Find the median of the two sorted arrays. The overall run time complexity should be O(log (m+n)).

Analyze

total = nums1.count + nums2.count
若total为奇数，median为数组并集的第total/2个元素；
若为偶数，则median =(并集的第total/2个元素+第(total/2+1)个元素 ) / 2

利用递归函数获取第两数组并集的第k个元素大小
假设k为偶数，
若nums1[k/2-1] > nums2[k/2-1]，则排除nums2的前k/2个元素，k -= k/2-1。
若nums1[k/2-1] < nums2[k/2-1]，则排除nums1的前k/2个元素，k -= k/2-1。
依照这个原则递归，排除两数组并集的前k-1个元素，从而获得第k个元素大小

递归函数终止条件：

• 当 nums1或 nums2为空时，分别返回 nums1[k-1]和nums2[k-1]；
• 当 k=1 是，返回 min(nums1[0], nums2[0])；
• 当 nums1[k/2-1]==nums2[k/2-1] 时，返回 �nums1[k/2-1]或nums2[k/2-1]

Code

class Solution {
    func findMedianSortedArrays(nums1: [Int], _ nums2: [Int]) -> Double {
        
        func find_kth(k: Int, nums1: [Int], nums2: [Int]) -> Double? {
         
            if k > nums1.count + nums2.count { return nil }
            // 令nums1元素的个数总是小等于nums2
            if nums1.count > nums2.count { return find_kth(k, nums1: nums2, nums2: nums1) }
            
            if nums1.count == 0 { return Double(nums2[k-1]) }
            
            if k == 1 { return Double(min(nums1[0], nums2[0])) }
            
            let i1 = min(k/2, nums1.count), i2 = k - i1
            print(nums1[i1-1], nums2[i2-1])
            if nums1[i1-1] < nums2[i2-1] {
                var nums1 = nums1
                nums1.removeRange(0..<i1)
                return find_kth(k-i1, nums1: nums1, nums2: nums2)
            }
            else if nums1[i1-1] > nums2[i2-1] {
                var nums2 = nums2
                nums2.removeRange(0..<i2)
                return find_kth(k-i2, nums1: nums1, nums2: nums2)
            }
            else {
                return Double(nums1[i1-1])
            }
        }
        
        let total = nums1.count + nums2.count
        if total % 2 != 0 {
            return find_kth(total / 2 + 1, nums1: nums1, nums2: nums2)!
        }
        else {
            return (find_kth(total / 2, nums1: nums1, nums2: nums2)! + find_kth(total / 2 + 1, nums1: nums1, nums2: nums2)! ) / 2.0
        }
    }
}