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;
}
}
``````