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
Median of two sorted arrays leetcode java
class Solution {
public double findMedianSortedArrays(int[] A, int[] B) {
int m = A.length;
int n = B.length;
if(m > n) {
int[]temp = A; A = B; B = temp;
int tmp = m; m = n; n = tmp;
}
int iMin = 0, iMax = m, halfLen = (m + n + 1) / 2;
while (iMin <= iMax) {
int i = (iMin + iMax) / 2;
int j = halfLen - i;
if(i < iMax && B[j-1] > A[i]) {
iMin = i + 1;
}
else if (i > iMin && A[i-1] > B[j]) {
iMax = i - 1;
}
else {
int maxLeft = 0;
if(i == 0) { maxLeft = A[i-1];}
else if(j == 0) { maxLeft = A[i-1];}
else { maxLeft = Math.max(A[i-1], B[j-1]);}
if( (m + n) % 2 == 1) { return maxLeft;}
int minRight = 0;
if(i == m) { minRight = B[j];}
else if(j == n) { minRight = A[i];}
else { minRight = Math.min(B[j], A[i]);}
return (maxLeft + minRight) / 2.0;
}
}
return 0.0;
}
}
Median of two sorted arrays leetcode python
import sys
from typing import List
def findMedianSortedArrays(nums1: List[int], nums2: List[int]) -> float:
# Check if nums1 is smaller than nums2
# If not, then we will swap it with nums2
if len(nums1) > len(nums2):
nums1, nums2 = nums2, nums1
# Lengths of two arrays
m = len(nums1)
n = len(nums2)
# Pointers for binary search
start = 0
end = m
# Binary search starts from here
while start <= end:
# Partition indices for both the arrays
partition_nums1 = (start + end) // 2
partition_nums2 = (m + n + 1) // 2 - partition_nums1
# Edge cases
# If there are no elements left on the left side after partition
maxLeftNums1 = -sys.maxsize if partition_nums1 == 0 else nums1[partition_nums1 - 1]
# If there are no elements left on the right side after partition
minRightNums1 = sys.maxsize if partition_nums1 == m else nums1[partition_nums1]
# Similarly for nums2
maxLeftNums2 = -sys.maxsize if partition_nums2 == 0 else nums2[partition_nums2 - 1]
minRightNums2 = sys.maxsize if partition_nums2 == n else nums2[partition_nums2]
# Check if we have found the match
if maxLeftNums1 <= minRightNums2 and maxLeftNums2 <= minRightNums1:
# Check if the combined array is of even/odd length
if (m + n) % 2 == 0:
return (max(maxLeftNums1, maxLeftNums2) + min(minRightNums1, minRightNums2)) / 2
else:
return max(maxLeftNums1, maxLeftNums2)
# If we are too far on the right, we need to go to left side
elif maxLeftNums1 > minRightNums2:
end = partition_nums1 - 1
# If we are too far on the left, we need to go to right side
else:
start = partition_nums1 + 1
# If we reach here, it means the arrays are not sorted
raise Exception("IllegalArgumentException")
Median of two sorted arrays javascript
var findMedianSortedArrays = function (nums1, nums2) {
// Check if num1 is smaller than num2
// If not, then we will swap num1 with num2
if (nums1.length > nums2.length) {
return findMedianSortedArrays(nums2, nums1);
}
// Lengths of two arrays
const m = nums1.length;
const n = nums2.length;
// Pointers for binary search
let start = 0;
let end = m;
// Binary search starts from here
while (start <= end) {
// Partitions of both the array
let partitionNums1 = Math.floor((start + end) / 2);
let partitionNums2 = Math.floor((m + n + 1) / 2) - partitionNums1;
// Edge cases
// If there are no elements left on the left side after partition
let maxLeftNums1 = partitionNums1 == 0 ? Number.MIN_SAFE_INTEGER : nums1[partitionNums1 - 1];
// If there are no elements left on the right side after partition
let minRightNums1 = partitionNums1 == m ? Number.MAX_SAFE_INTEGER : nums1[partitionNums1];
// Similarly for nums2
let maxLeftNums2 = partitionNums2 == 0 ? Number.MIN_SAFE_INTEGER : nums2[partitionNums2 - 1];
let minRightNums2 = partitionNums2 == n ? Number.MAX_SAFE_INTEGER : nums2[partitionNums2];
// Check if we have found the match
if (maxLeftNums1 <= minRightNums2 && maxLeftNums2 <= minRightNums1) {
// Check if the combined array is of even/odd length
if ((m + n) % 2 == 0) {
return (Math.max(maxLeftNums1, maxLeftNums2) + Math.min(minRightNums1, minRightNums2)) / 2.0;
} else {
return Math.max(maxLeftNums1, maxLeftNums2);
}
}
// If we are too far on the right, we need to go to left side
else if (maxLeftNums1 > minRightNums2) {
end = partitionNums1 - 1;
}
// If we are too far on the left, we need to go to right side
else {
start = partitionNums1 + 1;
}
}
};
Median of two sorted arrays leetcode solution c++
#include <bits/stdc++.h>
using namespace std;
double findMedianSortedArrays(vector<int>& A, vector<int>& B) {
long n = A.size(), m = B.size(), t=(n+m+1)/2;
if(n>m)return findMedianSortedArrays(B,A);
if(n==0) return m % 2 == 0 ? (double)(B[m/2 - 1] + B[m/2]) / 2 : B[m/2];
if(m==0) return n % 2 == 0 ? (double)(A[n/2 - 1] + A[n/2]) / 2 : A[n/2];
long left = 0, right = n;
while (left <= right) {
long partitionA = left + (right-left)/2;
long partitionB = t - double(partitionA);
double maxLeftA = INT_MIN;
if(partitionA > 0){
maxLeftA = A[partitionA-1];
}
double minRightA = INT_MAX;
if(partitionA < n){
minRightA = A[partitionA];
}
double maxLeftB = INT_MIN;
if(partitionB > 0){
maxLeftB = B[partitionB-1];
}
double minRightB = INT_MAX;
if(partitionB < m){
minRightB = B[partitionB];
}
if (maxLeftA <= minRightB && maxLeftB <= minRightA) {
if ((n+m) % 2 == 0) {
return (max(maxLeftA, maxLeftB) + min(minRightA, minRightB))/2.0;
}
else {
return max(maxLeftA, maxLeftB);
}
}
else if (maxLeftA > minRightB) {
right = partitionA - 1;
}
else {
left = partitionA + 1;
}
}
return 0.0;
}
int main() {
vector<int> A = {1, 2, 3, 5, 6};
vector<int> B = {4};
cout<<findMedianSortedArrays(A, B);
return 0;
}
Median of two sorted arrays in c
double findMedianSortedArrays(int* nums1, int nums1Size, int* nums2, int nums2Size){
int len = nums1Size + nums2Size;
int merged[len];
int i = 0, j = 0, idx = 0;
while (i < nums1Size || j < nums2Size) {
if (i < nums1Size && j < nums2Size) {
if (nums1[i] < nums2[j]) {
merged[idx++] = nums1[i++];
} else {
merged[idx++] = nums2[j++];
}
} else if (i < nums1Size) {
merged[idx++] = nums1[i++];
} else {
merged[idx++] = nums2[j++];
}
}
if (len % 2 == 0) {
return ((merged[len/2 - 1] + merged[len/2]) / 2.0);
} else {
return merged[len/2];
}
}
