4. 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
solution 1
merge array1 and array2, then return the median.
Time complexity: O(m+n)
Space complexity: O( m+n )
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
|
class Solution {
public double findMedianSortedArrays(int[] nums1, int[] nums2) {
int m = nums1.length;
int n = nums2.length;
int[] nums = new int[m+n];
if(m == 0){
if(n % 2 == 0){
return (nums2[n/2 - 1] + nums2[n/2]) / 2.0;
}else{
return nums2[n/2];
}
}
if( n == 0){
if(m % 2 == 0){
return (nums1[m/2 -1] + nums1[m/2]) / 2.0;
}else{
return nums1[m/2];
}
}
int count = 0;
int i = 0;
int j = 0;
while(count != (m+n)){
if(i == m){
while( j != n){
nums[count++] = nums2[j++];
}
break;
}
if(j == n){
while(i != m){
nums[count++] = nums1[i++];
}
break;
}
if(nums1[i] < nums2[j]){
nums[count++] = nums1[i++];
}else{
nums[count++] = nums2[j++];
}
}
if(count %2 == 0){
return (nums[count/2 - 1] + nums[count/2]) / 2.0;
}else{
return nums[count/2];
}
}
}
|
