preface

Our community will continue to add Yi Gu (Netflix growth hacker, author of “The Way to Interview for iOS”, ACE professional fitness coach. Swift algorithm solution sorted into text version to facilitate everyone to learn and read.

We have updated 3 issues of LeetCode algorithm so far, and we will keep the update time and progress (Monday, Wednesday and Friday at 9:00 a.m.). There is not much content in each issue, so we hope you can read it on your way to work, and there will be great improvement in long-term accumulation.

Short step, no thousands of miles; No small streams, no rivers and seas, Swift community with you forward. If you have suggestions and comments welcome to leave a message at the end of the article, we will try our best to meet your needs.

Difficulty level: Difficult

describe

Given two ordered arrays nums1 and nums2, their data length is n and m respectively, merge the two arrays into a new array, return the middle value of the new array.

The overall running time should be order log of m plus n.

The sample

Example 1

Input: nums1 = [1,3], nums2 = [2] output: 2.00000 description: the new array is [1,2,3] and the middle value is 2Copy the code

Example 2

Input: nums1 = [1,2], nums2 = [3,4] output: 2.50000 description: the new array is [1,2,3,4]. The median value is (2 + 3) / 2 = 2.5Copy the code

Example 3

Input: nums1 = [0,0], nums2 = [0,0] output: 0.00000Copy the code

Example 4

Input: nums1 = [], nums2 = [1] Output: 1.00000Copy the code

Example 5

Input: nums1 = [2], nums2 = [] Output: 2.00000Copy the code

limit

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

The answer

 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}}Copy the code
  • Time complexity: O(log(n + m))
  • Space complexity: O(1)
  • Main idea: ** For arrays of m and N numbers,nums1 和 nums2, includingm <= n. Want to be innums1Found in themid1Index to divide the array into left and right parts:

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

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

After several components, the left and right parts should ensure that:

  • Left equals right
  • Maximum on the left <= minimum on the right

Click to go to LeetCode practice

The github repository address for this algorithm is: github.com/soapyigu/Le…