4. Median of Two Sorted Arrays
- Total Accepted: 104147
- Total Submissions: 539044
- Difficulty: Hard
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:
代码语言：javascript复制nums1 = [1, 3]
nums2 = [2]
The median is 2.0Example 2:
代码语言：javascript复制nums1 = [1, 2]
nums2 = [3, 4]
The median is (2 3)/2 = 2.5
其实整个思路应该就是将两个有序数组进行排序的过程，然后根据总个数的奇偶决定中位数是一个还是两个的平均值。 1 public class No_4 {
2 public double findMedianSortedArrays(int[] nums1, int[] nums2) {
3 int total = nums1.length nums2.length ;
4 int [] res ;
5 //判断最后的结果是单独一个数还是两个数的平均值
6 if(total%2 == 1){
7 res = new int [1] ;
8 }else{
9 res = new int [2] ;
10 }
11 int count = 0 ; //当前值是第count小的数
12 int i = 0 ; //nums1的下标
13 int j = 0 ; //nums2的下标
14 int k = 0 ; //res的下标
15 int min ;
16 /*
17 * 将两个有序数组进行排序的过程
18 * 当total为偶数时，结果为总数的第 （total-1）/2 1个数和第（total-1）/2 2个数
19 * 当total为基数时，结果为总数的第（total-1）/2 1个数
20 * 所以，当count > （total-1）/2 时，开始存储，直到res存满为止
21 */
22 while((i < nums1.length ) && (j < nums2.length) && (k < res.length)){
23 count ;
24 min = nums1[i] > nums2[j] ? nums2[j ] : nums1[i ] ;
25 if(count > (total-1)/2){
26 res[k ] = min ;
27 }
28 }
29 //考虑nums2先排除完而没有完全得到需要的结果的情况
30 while((i < nums1.length ) && (k < res.length)){
31 count ;
32 min = nums1[i ] ;
33 if(count > (total-1)/2){
34 res[k ] = min ;
35 }
36 }
37 //考虑nums1先排除完而没有完全得到需要的结果的情况
38 while((j < nums2.length ) && (k < res.length)){
39 count ;
40 min = nums2[j ] ;
41 if(count > (total-1)/2){
42 res[k ] = min ;
43 }
44 }
45
46 //返回结果
47 if(total%2 == 1){
48 return res[0] ;
49 }else{
50 return ((res[0] res[1])/2.0) ;
51 }
52 }
53 }
