LeetCode -求两个有序数组的中间值
前言
我们社区陆续会将顾毅(Netflix 增长黑客，求两《iOS 面试之道》作者，序数ACE 职业健身教练。组的中间值微博:@故胤道长[1])的求两 Swift 算法题题解整理为文字版以方便大家学习与阅读。
LeetCode 算法到目前我们已经更新了 3 期，序数我们会保持更新时间和进度(周一、组的中间值周三、求两周五早上 9:00 发布)，序数每期的组的中间值内容不多，我们希望大家可以在上班路上阅读，求两长久积累会有很大提升。序数
该算法题解的亿华云组的中间值 github 仓库地址是：https://github.com/soapyigu/LeetCode-Swift[2]
不积跬步，无以至千里;不积小流，求两无以成江海，序数Swift社区 伴你前行。组的中间值如果大家有建议和意见欢迎在文末留言，我们会尽力满足大家的需求。
难度水平：困难
描述
已知两个有序数组 nums1 和 nums2，他们的数据长度分别是 n 和 m，将两个数组合并成一个新数组，返回新数组的云服务器提供商中间值。
整体的运行时间复杂度应该是 O(log (m+n))
示例
示例 1
输入：nums1 = [1,3], nums2 = [2] 输出：2.00000 说明：合并后的新数组为 [1,2,3]，中间值为 2示例 2
输入：nums1 = [1,2], nums2 = [3,4] 输出：2.50000 说明：合并后的新数组为 [1,2,3,4]，中间值为 (2 + 3) / 2 = 2.5示例 3
输入：nums1 = [0,0], nums2 = [0,0] 输出：0.00000示例 4
输入：nums1 = [], nums2 = [1] 输出：1.00000示例 5
输入：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 练习 https://leetcode.com/problems/median-of-two-sorted-arrays/
参考资料
[1]@故胤道长: https://m.weibo.cn/u/1827884772[2]LeetCode-Swift: https://github.com/soapyigu/LeetCode-Swift
本文转载自微信公众号「Swift社区」
