LeetCode -求兩個(gè)有序數(shù)組的中間值
前言
我們社區(qū)陸續(xù)會(huì)將顧毅(Netflix 增長黑客，《iOS 面試之道》作者，ACE 職業(yè)健身教練。微博:@故胤道長[1])的 Swift 算法題題解整理為文字版以方便大家學(xué)習(xí)與閱讀。
LeetCode 算法到目前我們已經(jīng)更新了 3 期，我們會(huì)保持更新時(shí)間和進(jìn)度(周一、周三、周五早上 9:00 發(fā)布)，每期的內(nèi)容不多，我們希望大家可以在上班路上閱讀，長久積累會(huì)有很大提升。
該算法題解的 github 倉庫地址是：https://github.com/soapyigu/LeetCode-Swift[2]
不積跬步，無以至千里;不積小流，無以成江海，Swift社區(qū) 伴你前行。如果大家有建議和意見歡迎在文末留言，我們會(huì)盡力滿足大家的需求。
難度水平：困難
描述
已知兩個(gè)有序數(shù)組 nums1 和 nums2，他們的數(shù)據(jù)長度分別是 n 和 m，將兩個(gè)數(shù)組合并成一個(gè)新數(shù)組，返回新數(shù)組的中間值。
整體的運(yùn)行時(shí)間復(fù)雜度應(yīng)該是 O(log (m+n))
示例
示例 1
- 輸入：nums1 = [1,3], nums2 = [2]
- 輸出：2.00000
- 說明：合并后的新數(shù)組為 [1,2,3]，中間值為 2
示例 2
- 輸入：nums1 = [1,2], nums2 = [3,4]
- 輸出：2.50000
- 說明：合并后的新數(shù)組為 [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
- }
- 時(shí)間復(fù)雜度：O(log(n + m))
- 空間復(fù)雜度：O(1)
- 主要思想：** 對于 m 和 n 數(shù)字的數(shù)組，nums1 和 nums2，其中 m <= n。要在 nums1 中找到 mid1 的索引，將數(shù)組分成左右部分：
nums1[0, 1, ..., mid1 - 1] | nums1[mid1, mid1 + 1, ..., m]
nums2[0, 1, ..., mid2 - 1] | nums2[mid2, mid2 + 1, ..., n]
數(shù)組分后的左右部分要確保：
- 左數(shù) = 右數(shù)
- 左邊的最大值 <= 右邊的最小值
前往 LeetCode 練習(xí) 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
本文轉(zhuǎn)載自微信公眾號「Swift社區(qū)」
