Swift-Median of Two Sorted Array

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)).

Example 1:

nums1 = [1, 3]
nums2 = [2]

The median is 2.0`</code></pre>

Example 2:
<pre><code>`nums1 = [1, 2]
nums2 = [3, 4]

The median is (2 + 3)/2 = 2.5

如果不考虑时间复杂度，最简单就是将两个数组合并，然后寻找中位数:

func findMedianSortedArrays(_ nums1: [Int], _ nums2: [Int]) -> Double {
        
        var index1:Int = 0
        var index2:Int = 0
        
        var preNum = 0
        var currentNum = 0
        
        var count:Int = 0
        
        let count1 = nums1.count
        let count2 = nums2.count
        
        let midIndex = (count1 + count2) / 2
        
        while index1 < count1 && index2 < count2 {
            
            if count - 1 == midIndex {
                break
            }
            
            preNum = currentNum
        
            if nums1[index1] < nums2[index2] {
                currentNum = nums1[index1]
                index1 += 1
            } else {
                currentNum = nums2[index2]
                index2 += 1
            }
            
            count += 1
        }
        
        while index1 < count1 {

            if count - 1 == midIndex {
                break
            }
            preNum = currentNum
            currentNum = nums1[index1]
            index1 += 1
            count += 1
        }
        
        while index2 < count2 {
            if count - 1 == midIndex {
                break
            }
            preNum = currentNum
            currentNum = nums2[index2]
            index2 += 1
            count += 1
        }
        
        var result:Double = 0
        
        if (count1 + count2) % 2 == 0 {
            result = Double(preNum + currentNum) / 2.0
        } else {
            result = Double(currentNum)
        }

        return result
    }

按照题目要求的复杂度，可以通过二分法递归实现，找两个已排序数组的中位数，其实就是将两个有序数组有序合并后找第K小的数。而找第K小的数，可以将K平分到两个数组中，然后利用一个重要的结论：如果A[k/2-1]<B[k/2-1]，那么A[0]~A[k/2-1]一定在第k小的数的序列当中.

func findMedianSortedArrays3(_ nums1: [Int], _ nums2: [Int]) -> Double {
        
        let count = nums1.count + nums2.count
        
        if count % 2 == 1 {
            return findKth(num1: num1, m: num1.count, num2: num2, n: num2.count, k: count / 2 + 1)
        } else {
            let mid1:Double = findKth(num1: num1, m: num1.count, num2: num2, n: num2.count, k: count / 2 + 1)
            let mid2:Double = findKth(num1: num1, m: num1.count, num2: num2, n: num2.count, k: count / 2)
            return (mid1 + mid2) / 2
        }
    }
    
    func findKth(num1:[Int], m:Int, num2:[Int], n:Int, k:Int) -> Double {
        
        // 假定第一个数组为较小数组
        if m > n {
            return findKth(num1: num2, m: n, num2: num1, n: m, k: k)
        }
        
        if m == 0 {
            return Double(num2[k - 1])
        }
        
        if  k == 1 {
            return Double(min(num1[0], num2[0]))
        }
        
        let lenA = min(k / 2, m)
        let lenB = k - lenA
        
        if num1[lenA - 1] < num2[lenB - 1] {
          let temp:[Int] = num1
          return findKth(num1: Array(temp.suffix(from: lenA)), m: m - lenA, num2: num2, n: n, k: k - lenA)
        } else if num1[lenA - 1] > num2[lenB - 1] {
            let temp:[Int] = num2
           return findKth(num1: num1, m: m, num2:Array(temp.suffix(from: lenB)) , n: n - lenB, k: k - lenB)
        } else {
           return Double(num2[lenA - 1])
        }
    }

1. 保持num1是短的那一个数组，num2是长的
2. 平分k, 一半在num1，一半在num2 (如果num1的长度不足K/2,那就pa就指到最后一个）
3. 如果lenA的值 < lenB的值，那证明第K个数肯定不会出现在pa之前，递归，把num1数组pa之前的数据删除.同理递归砍B数组.
4. 递归到 m == 0(num1为空)返回 B[k - 1], 或者k == 1（找第一个数）就返回min(num1第一个数num2第一个数）