Median of Two Sorted Arrays

发表于 |

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

SOL1

由于两个数列都是有序的，直接merge两个数组再求中间值，复杂度O（n）。

  • 注意最后返回值做除法时，不能直接写/2，会自动进行转换变成int，提醒是要注意返回值的格式
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
class Solution {
    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        int i = 0;
        int j = 0;
        int k = 0;
        int[] array = new int[nums1.length+nums2.length];
        while(i<nums1.length && j<nums2.length){
            if(nums1[i]<nums2[j]){
                array[k]=nums1[i];
                k++;
                i++;
            } else {
                array[k]=nums2[j];
                k++;
                j++;
            }
        }
        while(i<nums1.length){
            array[k]=nums1[i];
            k++;
            i++;
        }
        while(j<nums2.length){
            array[k]=nums2[j];
            k++;
            j++;
        }
        //compute median
        if(array.length%2 ==1){
            return array[(int)(array.length/2)];
        } else {
            return (array[(array.length/2)]+array[(array.length/2)-1])/2.0; //！！！这里一定不能写/2，会自动变成int！！！
        }
        
    }
}

SOL2

题目要求里面是需要log(m+n)

log复杂度, 参考水中的鱼blog的思路, 使用二分法. 其实看到log复杂度应该能直接想到二分的思路.
脑死,好难,我再想想,思路想出来了竟然不会写我屮艸芔茻

我再想想!!!!