LeetCode OJ 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)).

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

Subscribe to see which companies asked this question

【题目分析】

给定两个升序排列的整数数组，找到这两个数组所有元素的中位数。

【思路】

【java代码】

 1 public class Solution {
 2     public double findMedianSortedArrays(int[] nums1, int[] nums2) {
 3         int[] A = nums1, B = nums2;
 4         int m = nums1.length, n = nums2.length;
 5         
 6         if(m > n){
 7             A = nums2; B = nums1;
 8             m = nums2.length; n = nums1.length;
 9         }
10         
11         if(n == 0) return 0;
12         
13         int mini = 0, maxi = m;
14         int i = 0, j = 0;
15         int maxofleft, minofright = 0;
16         
17         while(mini <= maxi){
18             i = (maxi - mini)/2 + mini;
19             j = (m + n + 1)/2 - i;
20             if(j > 0 && i < m && B[j-1] > A[i]){
21                 mini = i + 1;
22             }   //i is too small
23             else if(i > 0 && j < n && A[i-1] > B[j]){
24                 maxi = i - 1;
25             }   //i is too big
26             else{
27                 if(i == 0) maxofleft = B[j-1];
28                 else if(j == 0) maxofleft = A[i-1];
29                 else maxofleft = Math.max(A[i-1], B[j-1]);
30                 
31                 if((m + n)%2 == 1) return maxofleft;
32                 
33                 if(i == m) minofright = B[j];
34                 else if(j == n) minofright = A[i];
35                 else minofright = Math.min(B[j], A[i]);
36                 
37                 return (double)(maxofleft + minofright) / 2.0;
38             }
39         }
40         return 0;
41     }
42 }