Leetcode: 4. Median of Two Sorted Arrays
- Primary idea: Merge two sorted arrays then find the median value of the merged array
- Time Complexity: O((n+m)* log(n+m)): Time required to sort the array of size n+m
- Space Complexity: O(n+m) Creating a new array of size n+m.
func findMedianSortedArrays(_ nums1: [Int], _ nums2: [Int]) -> Double {
// the length of the merge array
let total = nums1.count + nums2.count
// indexes for iterating over the arrays during merge
var index = 0
var index1 = 0
var index2 = 0
// variable to store the merged array
var mergedArray: [Int] = []
var res: Double = 0
while total > 0 && index <= total / 2 {
// Ensure the indexes of nums1 and nums2 are within bounds
if index1 < nums1.count && index2 < nums2.count {
if nums1[index1] < nums2[index2] {
// add value of nums1 if it's smaller, increase index1 to prepare for the next comparision
mergedArray.append(nums1[index1])
index1 += 1
} else {
// add value of nums2 if it's smaller, increase index2 to prepare for the next comparision
mergedArray.append(nums2[index2])
index2 += 1
}
} else if index1 < nums1.count && index2 >= nums2.count {
// add the rest of nums1
mergedArray.append(nums1[index1])
index1 += 1
} else {
// add the rest of nums2
mergedArray.append(nums2[index2])
index2 += 1
}
// increase index for loop ending condition check
index += 1
}
if total > 0 {
if total % 2 == 1 {
// Get the middle element if total has odd number of elements
res = Double(mergedArray[total / 2])
} else {
// Get the median of 2 elements in the middle of the array when total has even number of elements
res = (Double(mergedArray[total / 2]) + Double(mergedArray[total / 2 - 1])) / 2
}
}
return res
}
findMedianSortedArrays([1,3], [2]) // 2
findMedianSortedArrays([1,2], [3,4]) // 2.5
findMedianSortedArrays([-5, 3, 6, 12, 15 ], [-12, -10, -6, -3, 4, 10]) // 3