4. Median of Two Sorted Arrays
Overall
Difficulty: Hard
Link: https://leetcode.com/problems/median-of-two-sorted-arrays/
Introduction
Median of Two Sorted Arrays is a first Hard problem in Leetcode. It provided two arrays "nums1" and "nums2" and the program need to find the median of these two sorted arrays.
The key point is combine these two arrays that can find a median of these two sorted arrays.
Problem Content
Given two sorted arrays nums1 and nums2 of size m and n respectively, return the median of the two sorted arrays.
The overall run time complexity should be O(log (m+n)).
Example 1:
Input: nums1 = [1,3], nums2 = [2] Output: 2.00000 Explanation: merged array = [1,2,3] and median is 2.
Example 2:
Input: nums1 = [1,2], nums2 = [3,4] Output: 2.50000 Explanation: merged array = [1,2,3,4] and median is (2 + 3) / 2 = 2.5.
Constraints:
nums1.length == m
nums2.length == n
0 <= m <= 1000
0 <= n <= 1000
1 <= m + n <= 2000
-106 <= nums1[i], nums2[i] <= 106
Concept
The problem is provide two array called "nums1" and "nums2" then the program need to return a median of these two sorted arrays.
First, we use "nums1.concat(nums2)" to combine two array as "merged_array" and use "merged_array.sort((a, b)=> a - b)" to sort them by increase order.
Then, if the length of "merged_array" is odd, it should return a number at middle point in the array("merged_array[(merged_array.length-1)/2]") as median. Otherwise return the average of two number at middle point in the array as median("merged_array[(merged_array.length-2)/2]+merged_array[(merged_array.length)/2])/2").
Solve(Javascript)
/**
* @param {number[]} nums1
* @param {number[]} nums2
* @return {number}
*/
var findMedianSortedArrays = function(nums1, nums2) {
let merged_array=nums1.concat(nums2);
merged_array.sort((a, b)=> a - b);
if(merged_array.length % 2==1){
return merged_array[(merged_array.length-1)/2];
}else{
return (merged_array[(merged_array.length-2)/2]+merged_array[(merged_array.length)/2])/2;
}
};