Algorithm
Problem Name: 4. Median of Two Sorted Arrays
Problem Link: https://leetcode.com/problems/median-of-two-sorted-arrays/
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 == mnums2.length == n0 <= m <= 10000 <= n <= 10001 <= m + n <= 2000-106 <= nums1[i], nums2[i] <= 106
Code Examples
#1 Code Example with C Programming
Code -
C Programming
int bs(int *n, int sz, int k) {
int i, j, m;
i = 0;
j = sz - 1;
while (i < = j) {
m = i + (j - i) / 2;
if (n[m] > k) {
j = m - 1;
} else {
i = m + 1;
}
}
return j; // this is the lastest one which is not greater than k
}
double bs2(int *n1, int sz1, int *n2, int sz2, int m, int m1) {
double d;
int i;
i = bs(n1, sz1, n2[0]); // search in first array
if (i >= m) { // median is in the first array
d = n1[m];
if (m1) {
if (i > m) {
d += n1[m + 1];
} else {
d += n2[0];
}
d /= 2;
}
} else if (i == sz1 - 1) { // median is in the second array
d = n2[m - i - 1];
if (m1) {
d += n2[m - i];
d /= 2;
}
} else { // reverse arrays and search again
d = bs2(n2, sz2, &n1[i + 1], sz1 - i - 1, m - i - 1, m1);
}
return d;
}
int min(int a, int b) {
return a < b ? a : b;
}
int max(int a, int b) {
return a > b ? a : b;
}
double findMedianSortedArrays(int* nums1, int nums1Size, int* nums2, int nums2Size) {
double d;
#if 0 // sliding & binary search
int i1_left = 0, i1_right = nums1Size;
int i1, i2;
if (nums1Size > nums2Size) { // make nums1 as a short array
return findMedianSortedArrays(nums2, nums2Size, nums1, nums1Size);
}
// O(log(min(m, n)))
while (i1_left < = i1_right) {
i1 = i1_left + (i1_right - i1_left) / 2;
i2 = (nums1Size + nums2Size + 1) / 2 - i1;
if (i1 > 0 && nums1[i1 - 1] > nums2[i2]) {
i1_right = i1 - 1;
} else if (i1 < nums1Size && nums1[i1] < nums2[i2 - 1]) {
i1_left = i1 + 1;
} else {
// found it!
if (i1 == 0) d = nums2[i2 - 1];
else if (i2 == 0) d = nums1[i1 - 1];
else if (nums1[i1 - 1] > nums2[i2 - 1]) d = nums1[i1 - 1];
else d = nums2[i2 - 1];
if (((nums1Size + nums2Size) % 2) == 0) {
if (i2 == nums2Size) {
d = (d + nums1[i1]) / 2;
} else if (i1 == nums1Size) {
d = (d + nums2[i2]) / 2;
} else if (nums1[i1] < nums2[i2]) {
d = (d + nums1[i1]) / 2;
} else {
d = (d + nums2[i2]) / 2;
}
}
break;
}
}
#else // binary search 40+ms
int p1, p2;
p1 = (nums1Size + nums2Size - 1) / 2;
p2 = ((nums1Size + nums2Size) % 2) ? 0 : 1;
if (nums2Size == 0) {
d = nums1[p1];
if (p2) {
d += nums1[p1 + 1];
d /= 2;
}
return d;
}
if (nums1Size == 0) {
d = nums2[p1];
if (p2) {
d += nums2[p1 + 1];
d /= 2;
}
return d;
}
if (nums2[0] < nums1[0]) return bs2(nums2, nums2Size, nums1, nums1Size, p1, p2);
return bs2(nums1, nums1Size, nums2, nums2Size, p1, p2);
#endif
return d;
}
Input
nums1 = [1,3], nums2 = [2]
Output
2.00000
#2 Code Example with C++ Programming
Code -
C++ Programming
class Solution {
public:
double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
int m = nums1.size(), n = nums2.size();
if(m > n) return findMedianSortedArrays(nums2, nums1);
int lo = 0, hi = m, mid = (m + n + 1)/2;
while(lo <= hi){
int i = (lo + hi>/2;
int j = mid - i;
if(i < m && nums2[j - 1] > nums1[i])
lo = i + 1;
else if(i > 0 && nums1[i - 1] > nums2[j])
hi = i - 1;
else{
int maxLeft = (i == 0) ? nums2[j - 1] : (j == 0) ? nums1[i - 1] : max(nums1[i - 1], nums2[j - 1]);
int minRight = (i == m) ? nums2[j] : (j == n) ? nums1[i] : min(nums1[i], nums2[j]);
return (m + n) % 2 ? maxLeft : (maxLeft + minRight) / 2.0;
}
}
}
};
Input
nums1 = [1,2], nums2 = [3,4]
Output
2.50000
#3 Code Example with Java Programming
Code -
Java Programming
class Solution {
public double findMedianSortedArrays(int[] nums1, int[] nums2) {
int n = nums1.length + nums2.length;
ArrayList < Integer> arr = new ArrayList<>();
int i = 0;
int j = 0;
int k = 0;
int limit = (n)/2 + 1;
while (i < nums1.length && j < nums2.length && k < limit) {
if (nums1[i] < nums2[j]) {
arr.add(nums1[i]);
i++;
}
else {
arr.add(nums2[j]);
j++;
}
k++;
}
if (i < nums1.length) {
while (i < nums1.length && k < limit) {
arr.add(nums1[i]);
i++;
k++;
}
}
else {
while (j < nums2.length && k < limit) {
arr.add (nums2[j]);
j++;
k++;
}
}
k--;
return n%2 == 0 ? (double) (arr.get(k - 1) + arr.get(k)) / 2.0 : (double) arr.get(k);
}
}
Input
nums1 = [1,3], nums2 = [2]
Output
2.00000
#4 Code Example with Javascript Programming
Code -
Javascript Programming
const findMedianSortedArrays = function(A, B) {
let m = A.length,
n = B.length;
if (m > n) {
return findMedianSortedArrays(B, A);
}
let imin = 0,
imax = m,
i,
j;
while (imin < = imax) {
i = (imin + imax) >> 1;
j = ((m + n + 1) >> 1) - i;
if (j > 0 && i < m && B[j - 1] > A[i]) {
imin = i + 1;
} else if (i > 0 && j < n && A[i - 1] > B[j]) {
imax = i - 1;
} else {
if (i === 0) {
num1 = B[j - 1];
} else if (j === 0) {
num1 = A[i - 1];
} else {
num1 = Math.max(A[i - 1], B[j - 1]);
}
if ((m + n) & 1) {
return num1;
}
if (i === m) {
num2 = B[j];
} else if (j === n) {
num2 = A[i];
} else {
num2 = Math.min(A[i], B[j]);
}
return (num1 + num2) / 2.0;
}
}
};
Input
nums1 = [1,2], nums2 = [3,4]
Output
2.50000
#5 Code Example with Python Programming
Code -
Python Programming
class Solution:
def findMedianSortedArrays(self, nums1, nums2):
arr = sorted(nums1 + nums2)
if len(arr) % 2 == 0: return (arr[len(arr) // 2] + arr[len(arr) // 2 - 1]) / 2
else: return arr[len(arr) // 2]
Input
nums1 = [1,3], nums2 = [2]
Output
2.00000
#6 Code Example with C# Programming
Code -
C# Programming
namespace LeetCode
{
public class _004_MedianOfTwoSortedArrays
{
public double FindMedianSortedArrays(int[] nums1, int[] nums2)
{
int m = nums1.Length + nums2.Length;
if (m % 2 == 1)
return FindKth(nums1, 0, nums2, 0, (m + 1) / 2);
else
return (FindKth(nums1, 0, nums2, 0, (m + 1) / 2) + FindKth(nums1, 0, nums2, 0, (m + 1) / 2 + 1)) / 2;
}
double FindKth(int[] nums1, int startIndex1, int[] nums2, int startIndex2, int k)
{
var nums1Left = nums1.Length - startIndex1;
var nums2Left = nums2.Length - startIndex2;
if (nums1Left < nums2Left) { return FindKth(nums2, startIndex2, nums1, startIndex1, k); }
if (nums2.Length <= startIndex2) { return nums1[startIndex1 + k - 1]; }
if (k == 1) { return nums1[startIndex1] < nums2[startIndex2] ? nums1[startIndex1] : nums2[startIndex2]; }
var index1 = k / 2 < nums1Left ? k / 2 : nums1Left;
var index2 = k - index1 < nums2Left ? k - index1 : nums2Left;
if (nums1[index1 + startIndex1 - 1] > nums2[index2 + startIndex2 - 1])
return FindKth(nums1, startIndex1, nums2, index2 + startIndex2, k - index2);
else if (nums1[index1 + startIndex1 - 1] < nums2[index2 + startIndex2 - 1])
return FindKth(nums1, index1 + startIndex1, nums2, startIndex2, k - index1);
else
{
if (index1 + index2 == k)
return nums1[index1 + startIndex1 - 1];
return FindKth(nums1, index1 + startIndex1, nums2, index2 + startIndex2, k - index1 - index2);
}
}
}
}
Input
nums1 = [1,2], nums2 = [3,4]
Output
2.50000