4. Median of Two Sorted Arrays (Hard)
https://leetcode.com/problems/median-of-two-sorted-arrays/
There are two sorted arrays nums1 and nums2 of size m and n respectively.
Find the median of the two sorted arrays. The overall run time complexity should be O(log (m+n)).
You may assume nums1 and nums2 cannot be both empty.
Example 1:
nums1 = [1, 3] nums2 = [2] The median is 2.0
Example 2:
nums1 = [1, 2] nums2 = [3, 4] The median is (2 + 3)/2 = 2.5
Solutions
1.
class Solution {
// As a matter of fact, this problem is not that difficult, it should be tagged as easy.
public double findMedianSortedArrays(int[] nums1, int[] nums2) {
int len1 = nums1.length;
int len2 = nums2.length;
int totalLen = len1 + len2;
int pos1 = totalLen / 2;
int pos2 = totalLen / 2 + 1;
if (totalLen % 2 == 1) {
pos1 = pos2;
}
int med1 = 0;
int med2 = 0;
int i = 0;
int j = 0;
int count = 0;
while (count < totalLen) {
while (i < len1 && j < len2) {
int val;
if (nums1[i] < nums2[j]) {
val = nums1[i++];
} else {
val = nums2[j++];
}
count++;
if (count == pos1) {
med1 = val;
}
if (count == pos2) {
med2 = val;
}
}
while (i < len1) {
count++;
if (count == pos1) {
med1 = nums1[i];
}
if (count == pos2) {
med2 = nums1[i];
}
i++;
}
while (j < len2) {
count++;
if (count == pos1) {
med1 = nums2[j];
}
if (count == pos2) {
med2 = nums2[j];
}
j++;
}
}
return (med1 * 1l + med2 * 1l) / 2.0;
}
}
2.
class Solution {
public double findMedianSortedArrays(int[] nums1, int[] nums2) {
int len1 = nums1.length;
int len2 = nums2.length;
int totalLen = len1 + len2;
boolean isOdd = true;
if (totalLen % 2 == 0) {
isOdd = false;
}
int[] tmp = new int[totalLen];
int count = 0;
int i = 0;
int j = 0;
while (count < totalLen) {
if (i < len1 && j < len2 && nums1[i] <= nums2[j]) {
tmp[count++] = nums1[i++];
} else if (i < len1 && j < len2 && nums1[i] >= nums2[j]) {
tmp[count++] = nums2[j++];
} else if (j == len2 && i < len1) {
tmp[count++] = nums1[i++];
} else if (i == len1 && j < len2) {
tmp[count++] = nums2[j++];
}
// pruning
if (totalLen >= 3 && count > (totalLen + 1) / 2) {
break;
}
}
if (isOdd) {
return tmp[(totalLen - 1) / 2];
}
return (tmp[totalLen / 2] * 1l + tmp[totalLen / 2 - 1] * 1l) / 2.0;
}
}