LeetCode - 4 求两个有序数组的中间值

LeetCode 题库：https://github.com/SwiftCommunityRes/LeetCode–Swift

前言

我们社区陆续会将顾毅（Netflix 增长黑客，《iOS 面试之道》作者，ACE 职业健身教练。微博:@故胤道长）的 Swift 算法题题解整理为文字版以方便大家学习与阅读。

LeetCode 算法到目前我们已经更新了 3 期，我们会保持更新时间和进度（周一、周三、周五早上 9:00 发布），每期的内容不多，我们希望大家可以在上班路上阅读，长久积累会有很大提升。

不积跬步，无以至千里；不积小流，无以成江海，Swift社区伴你前行。如果大家有建议和意见欢迎在文末留言，我们会尽力满足大家的需求。

难度水平：困难

描述

已知两个有序数组 nums1 和 nums2，他们的数据长度分别是 n 和 m，将两个数组合并成一个新数组，返回新数组的中间值。

整体的运行时间复杂度应该是 O(log (m+n))

示例

示例 1

1
2
3

输入：nums1 = [1,3], nums2 = [2]
输出：2.00000
说明：合并后的新数组为 [1,2,3]，中间值为 2

示例 2

1
2
3

输入：nums1 = [1,2], nums2 = [3,4]
输出：2.50000
说明：合并后的新数组为 [1,2,3,4]，中间值为 (2 + 3) / 2 = 2.5

示例 3

1 2	输入：nums1 = [0,0], nums2 = [0,0] 输出：0.00000

示例 4

1 2	输入：nums1 = [], nums2 = [1] 输出：1.00000

示例 5

1 2	输入：nums1 = [2], nums2 = [] 输出：2.00000

限制

nums1.length == m
nums2.length == n
0 <= m <= 1000
0 <= n <= 1000
1 <= m + n <= 2000
-106 <= nums1[i], nums2[i] <= 106

答案

 class Solution {
    func findMedianSortedArrays(_ nums1: [Int], _ nums2: [Int]) -> Double {
        let m = nums1.count
        let n = nums2.count
        
        if m > n {
            return findMedianSortedArrays(nums2, nums1)
        }

        var halfLength: Int = (m + n + 1) >> 1
        var b = 0, e = m
        var maxOfLeft = 0
        var minOfRight = 0
                
        while b <= e {
            let mid1 = (b + e) >> 1
            let mid2 = halfLength - mid1
            
            if mid1 > 0 && mid2 < n && nums1[mid1 - 1] > nums2[mid2] {
                e = mid1 - 1
            } else if mid2 > 0 && mid1 < m && nums1[mid1] < nums2[mid2 - 1] {
                b = mid1 + 1
            } else {
                if mid1 == 0 {
                    maxOfLeft = nums2[mid2 - 1]
                } else if mid2 == 0 {
                    maxOfLeft = nums1[mid1 - 1]
                } else {
                    maxOfLeft = max(nums1[mid1 - 1], nums2[mid2 - 1])
                }
                
                if (m + n) % 2 == 1 {
                    return Double(maxOfLeft)
                }
                
                if mid1 == m {
                    minOfRight = nums2[mid2]
                } else if mid2 == n {
                    minOfRight = nums1[mid1]
                } else {
                    minOfRight = min(nums1[mid1], nums2[mid2])
                }
                
                break
            }
        }
        return Double(maxOfLeft + minOfRight) / 2.0
    }
}

时间复杂度：O(log(n + m))
空间复杂度：O(1)
主要思想：** 对于 m 和 n 数字的数组，nums1 和 nums2，其中 m <= n。要在 nums1 中找到 mid1 的索引，将数组分成左右部分：

nums1[0, 1, ..., mid1 - 1] | nums1[mid1, mid1 + 1, ..., m]

nums2[0, 1, ..., mid2 - 1] | nums2[mid2, mid2 + 1, ..., n]

数组分后的左右部分要确保：

左数 = 右数
左边的最大值 <= 右边的最小值

点击前往 LeetCode 练习

关于我们

公众号是由 Swift 爱好者共同维护，我们会分享以 Swift 实战、SwiftUI、Swift 基础为核心的技术内容，也整理收集优秀的学习资料。欢迎关注公众号：Swift社区，后台点击进群，联系我们获取更多内容。

Swift社区