[[435416]]

前言

我們社區陸續會將顧毅(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社區」