leetcode 4. Median of Two Sorted Arrays

Seawolf

1. There are two sorted arrays nums1 and nums2 of size m and n respectively.
   
2. 
   
3. Find the median of the two sorted arrays. The overall run time complexity should be O(log (m+n)).
   
4. 
   
5. You may assume nums1 and nums2 cannot be both empty.
   
6. 
   
7. Example 1:
   
8. 
   
9. nums1 = [1, 3]
   
10. nums2 = [2]
    
11. 
    
12. The median is 2.0
    
13. Example 2:
    
14. 
    
15. nums1 = [1, 2]
    
16. nums2 = [3, 4]
    
17. 
    
18. The median is (2 + 3)/2 = 2.5

复制代码

1. class Solution {
   
2.     public double findMedianSortedArrays(int[] nums1, int[] nums2) {
   
3.         int m = nums1.length;
   
4.         int n = nums2.length;
   
5.         if(m > n){
   
6.             int[] temp = nums1;
   
7.             nums1 = nums2;
   
8.             nums2 = temp;
   
9.             int temp1 = m;
   
10.             m = n;
    
11.             n = temp1;
    
12.         }
    
13.         
    
14.         if(m == 0){
    
15.             if(n % 2 ==0) return (nums2[n/2 - 1] + nums2[n/2])/2.0;
    
16.             else return nums2[n/2]/1.0;
    
17.         }
    
18.         
    
19.         int start = 0;
    
20.         int end = m;
    
21.         int maxleft = 0;
    
22.         int minright = 0;
    
23.         int half = (m+n+1)/2;
    
24.         
    
25.         while (start <= end){
    
26.             int i = (start + end)/2;
    
27.             int j = half - i;
    
28.             if(i > 0 && nums1[i-1] > nums2[j]){
    
29.                 end = i - 1;
    
30.             }
    
31.             else if (i < m && nums1[i] < nums2[j-1]){
    
32.                 start = i + 1;
    
33.             }
    
34.             else{
    
35.                 if(i == 0) maxleft = nums2[j-1];
    
36.                 else if (j == 0) maxleft = nums1[i-1];
    
37.                 else maxleft = Math.max(nums2[j-1], nums1[i-1]);
    
38.                
    
39.                 if(i == m) minright = nums2[j];
    
40.                 else if (j == n) minright = nums1[i];
    
41.                 else minright = Math.min(nums2[j], nums1[i]);
    
42.                
    
43.                 if((m+n) % 2 == 0) return (minright + maxleft)/2.0;
    
44.                 else return maxleft/1.0;
    
45.             }
    
46.         }
    
47.         
    
48.         return -1.0;
    
49.     }
    
50. }
    

复制代码

1. class Solution:
   
2.     def findMedianSortedArrays(self, nums1: List[int], nums2: List[int]) -> float:
   
3.         m = len(nums1)
   
4.         n = len(nums2)
   
5.         if(m > n):
   
6.             temp = nums1
   
7.             nums1 = nums2
   
8.             nums2 = temp
   
9.             temp1 = m
   
10.             m = n
    
11.             n = temp1
    
12.         
    
13.         
    
14.         if(m == 0):
    
15.             if(n % 2 ==0):
    
16.                 return (nums2[int(n/2) - 1] + nums2[int(n/2)])/2.0
    
17.             else:
    
18.                 return (nums2[int(n/2)])/1.0
    
19.         
    
20.         
    
21.         start = 0
    
22.         end = m
    
23.         maxleft = 0
    
24.         minright = 0
    
25.         half = int((m+n+1)/2)
    
26.         
    
27.         while (start <= end):
    
28.             i = int((start + end)/2)
    
29.             j = half - i
    
30.             if(i > 0 and nums1[i-1] > nums2[j]):
    
31.                 end = i - 1
    
32.             
    
33.             elif (i < m and nums1[i] < nums2[j-1]):
    
34.                 start = i + 1
    
35.             
    
36.             else:
    
37.                 if(i == 0):
    
38.                     maxleft = nums2[j-1]
    
39.                 elif (j == 0):
    
40.                     maxleft = nums1[i-1]
    
41.                 else:
    
42.                     maxleft = max(nums2[j-1], nums1[i-1])
    
43.                
    
44.                 if(i == m):
    
45.                     minright = nums2[j]
    
46.                 elif (j == n):
    
47.                     minright = nums1[i]
    
48.                 else:
    
49.                     minright = min(nums2[j], nums1[i])
    
50.             
    
51.         
    
52.         
    
53.                 if((m+n) % 2 == 0):
    
54.                     return (minright + maxleft)/2.0
    
55.                 else:
    
56.                     return maxleft/1.0

复制代码