4. Median of Two Sorted Arrays
總的時間複雜度應為 O(log (m+n))。
Python
/**
* @param {number[]} nums1
* @param {number[]} nums2
* @return {number}
*/
var findMedianSortedArrays = function(nums1, nums2) {
// Ensure nums1 is the smaller array to make the binary search simpler
if (nums1.length > nums2.length) {
return findMedianSortedArrays(nums2, nums1);
}
let m = nums1.length;
let n = nums2.length;
let imin = 0, imax = m, halfLen = Math.floor((m + n + 1) / 2);
while (imin <= imax) {
let i = Math.floor((imin + imax) / 2);
let j = halfLen - i;
if (i < m && nums1[i] < nums2[j - 1]) {
// i is too small, must increase it
imin = i + 1;
} else if (i > 0 && nums1[i - 1] > nums2[j]) {
// i is too big, must decrease it
imax = i - 1;
} else {
// i is perfect
let maxOfLeft;
if (i === 0) { maxOfLeft = nums2[j - 1]; }
else if (j === 0) { maxOfLeft = nums1[i - 1]; }
else { maxOfLeft = Math.max(nums1[i - 1], nums2[j - 1]); }
if ((m + n) % 2 === 1) {
return maxOfLeft;
}
let minOfRight;
if (i === m) { minOfRight = nums2[j]; }
else if (j === n) { minOfRight = nums1[i]; }
else { minOfRight = Math.min(nums1[i], nums2[j]); }
return (maxOfLeft + minOfRight) / 2;
}
}
throw new Error("Input arrays are not sorted.");
};
52.61MB, 96ms
C++
#include <vector>
#include <algorithm>
using namespace std;
class Solution {
public:
double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
// Ensure nums1 is the smaller array to make the binary search simpler
if (nums1.size() > nums2.size()) {
return findMedianSortedArrays(nums2, nums1);
}
int m = nums1.size();
int n = nums2.size();
int imin = 0, imax = m, halfLen = (m + n + 1) / 2;
while (imin <= imax) {
int i = (imin + imax) / 2;
int j = halfLen - i;
if (i < m && nums1[i] < nums2[j - 1]) {
// i is too small, must increase it
imin = i + 1;
} else if (i > 0 && nums1[i - 1] > nums2[j]) {
// i is too big, must decrease it
imax = i - 1;
} else {
// i is perfect
int maxOfLeft;
if (i == 0) { maxOfLeft = nums2[j - 1]; }
else if (j == 0) { maxOfLeft = nums1[i - 1]; }
else { maxOfLeft = max(nums1[i - 1], nums2[j - 1]); }
if ((m + n) % 2 == 1) {
return maxOfLeft;
}
int minOfRight;
if (i == m) { minOfRight = nums2[j]; }
else if (j == n) { minOfRight = nums1[i]; }
else { minOfRight = min(nums1[i], nums2[j]); }
return (maxOfLeft + minOfRight) / 2.0;
}
}
throw invalid_argument("Input arrays are not sorted.");
}
};
94.47MB, 25ms
Javascript
/**
* @param {number[]} nums1
* @param {number[]} nums2
* @return {number}
*/
var findMedianSortedArrays = function(nums1, nums2) {
// Ensure nums1 is the smaller array to make the binary search simpler
if (nums1.length > nums2.length) {
return findMedianSortedArrays(nums2, nums1);
}
let m = nums1.length;
let n = nums2.length;
let imin = 0, imax = m, halfLen = Math.floor((m + n + 1) / 2);
while (imin <= imax) {
let i = Math.floor((imin + imax) / 2);
let j = halfLen - i;
if (i < m && nums1[i] < nums2[j - 1]) {
// i is too small, must increase it
imin = i + 1;
} else if (i > 0 && nums1[i - 1] > nums2[j]) {
// i is too big, must decrease it
imax = i - 1;
} else {
// i is perfect
let maxOfLeft;
if (i === 0) { maxOfLeft = nums2[j - 1]; }
else if (j === 0) { maxOfLeft = nums1[i - 1]; }
else { maxOfLeft = Math.max(nums1[i - 1], nums2[j - 1]); }
if ((m + n) % 2 === 1) {
return maxOfLeft;
}
let minOfRight;
if (i === m) { minOfRight = nums2[j]; }
else if (j === n) { minOfRight = nums1[i]; }
else { minOfRight = Math.min(nums1[i], nums2[j]); }
return (maxOfLeft + minOfRight) / 2;
}
}
throw new Error("Input arrays are not sorted.");
};
54.49MB, 78ms
