前言
我们社区陆续会将顾毅(Netflix 增长黑客,《iOS 面试之道》作者,ACE 职业健身教练。)的 Swift 算法题题解整理为文字版以方便大家学习与阅读。
LeetCode 算法到目前我们已经更新了 3 期,我们会保持更新时间和进度(周一、周三、周五早上 9:00 发布),每期的内容不多,我们希望大家可以在上班路上阅读,长久积累会有很大提升。
不积跬步,无以至千里;不积小流,无以成江海,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 练习
该算法题解的 github 仓库地址是:https://github.com/soapyigu/LeetCode-Swift