leetcode 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 =
nums2 =
The median is 2.0
Example 2:
nums1 =
nums2 =
The median is (2 + 3)/2 = 2.5
class Solution {
public double findMedianSortedArrays(int[] nums1, int[] nums2) {
int m = nums1.length;
int n = nums2.length;
if(m > n){
int[] temp = nums1;
nums1 = nums2;
nums2 = temp;
int temp1 = m;
m = n;
n = temp1;
}
if(m == 0){
if(n % 2 ==0) return (nums2 + nums2)/2.0;
else return nums2/1.0;
}
int start = 0;
int end = m;
int maxleft = 0;
int minright = 0;
int half = (m+n+1)/2;
while (start <= end){
int i = (start + end)/2;
int j = half - i;
if(i > 0 && nums1 > nums2){
end = i - 1;
}
else if (i < m && nums1 < nums2){
start = i + 1;
}
else{
if(i == 0) maxleft = nums2;
else if (j == 0) maxleft = nums1;
else maxleft = Math.max(nums2, nums1);
if(i == m) minright = nums2;
else if (j == n) minright = nums1;
else minright = Math.min(nums2, nums1);
if((m+n) % 2 == 0) return (minright + maxleft)/2.0;
else return maxleft/1.0;
}
}
return -1.0;
}
}
class Solution:
def findMedianSortedArrays(self, nums1: List, nums2: List) -> float:
m = len(nums1)
n = len(nums2)
if(m > n):
temp = nums1
nums1 = nums2
nums2 = temp
temp1 = m
m = n
n = temp1
if(m == 0):
if(n % 2 ==0):
return (nums2 + nums2)/2.0
else:
return (nums2)/1.0
start = 0
end = m
maxleft = 0
minright = 0
half = int((m+n+1)/2)
while (start <= end):
i = int((start + end)/2)
j = half - i
if(i > 0 and nums1 > nums2):
end = i - 1
elif (i < m and nums1 < nums2):
start = i + 1
else:
if(i == 0):
maxleft = nums2
elif (j == 0):
maxleft = nums1
else:
maxleft = max(nums2, nums1)
if(i == m):
minright = nums2
elif (j == n):
minright = nums1
else:
minright = min(nums2, nums1)
if((m+n) % 2 == 0):
return (minright + maxleft)/2.0
else:
return maxleft/1.0
页:
[1]