LeetCode: 4. Median of Two Sorted Arrays

LeetCode: 4. Median of Two Sorted Arrays

Problem: 4. Median of Two Sorted Arrays

Link: https://leetcode.com/problems/median-of-two-sorted-arrays/

Difficulty: Hard

Description:

There are two sorted arrays nums1 and nums2 of size m and n respectively.
Find the median of the two sorted arrays. The overall run time complexity should be O(log (m+n)).
You may assume nums1 and nums2 cannot be both empty.

Example 1:

nums1 = [1, 3] nums2 = [2] The median is 2.0

Example 2:

nums1 = [1, 2] nums2 = [3, 4] The median is (2 + 3)/2 = 2.5

Solution:

Language: Swift

Runtime: 104ms
Memory: 4.0MB

Copy to Clipboard

class Solution {
    func findMedianSortedArrays(_ nums1: [Int], _ nums2: [Int]) -> Double {
        var length = nums1.count + nums2.count
        var middle = length / 2 + 1
        var index = 0
        var i = 0
        var j = 0
        var middle_left = min(nums1.first ?? Int.max, nums2.first ?? Int.max)
        var middle_right = middle_left

while i < nums1.count && j < nums2.count && index < middle {
            index += 1
            middle_left = middle_right
            if nums1[i] < nums2[j] {
                
                middle_right = nums1[i]
                i += 1
            } else {
                
                middle_right = nums2[j]
                j += 1
            }
        }
        
        while j < nums2.count && index < middle {
            index += 1
            middle_left = middle_right
            middle_right = nums2[j]
            j += 1
        }
        
        while i < nums1.count && index < middle {
            index += 1
            middle_left = middle_right
            middle_right = nums1[i]
            i += 1
        }
    
        if length % 2 == 0 {
            return Double(middle_left + middle_right)/2
        } else {
            return Double(middle_right)
        }
    }
}

Related Posts

Leave A Comment Cancel reply