LeetCode 题解-4. Median of Two Sorted Arrays

对Leetcode 4. Median of Two Sorted Arrays 题目的求解。

Problem Description#

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#

1
nums1 = [1, 3]
2
nums2 = [2]
3

4
The median is 2.0

Example 2#

1
nums1 = [1, 2]
2
nums2 = [3, 4]
3

4
The median is (2 + 3)/2 = 2.5

Analysis#

这道题是leetcode上第一道hard题目，其困难主要在于题意的理解和边界情况的处理上。

题意理解#

首先，我们要换一种方式来理解中位数。对于中位数，我们有两种理解

通过中位数可以将数组分为两半，使得前一半的元素都小于后一半的元素。
中位数即为第len/2个元素。

事实上，从两种不同的理解出发，我们可以得到两种不同的解法。基于第一种理解，我们可以不断进行二分查找，找到中间元素.而对于第二种理解，我们可以从两个数组的头部出发，寻找第len/2个元素．我们首先列出第二种理解对应的解法．其中index表示我们要在两个列表联合构成的集合中要找到的第index个元素．

边界情况分析#

Solution 1#

1
public static double findMedianSortedArrays(int[] nums1, int[] nums2) {
2
        int m = nums1.length;
3
        int n = nums2.length;
4
        if ( (m + n)% 2 == 0){
5
            int l = helper(nums1, nums2, 0, m-1, 0, n-1, (m+n)/2);
6
            int r = helper(nums1, nums2, 0, m-1, 0, n-1, (m+n)/2+1);
7
            //System.out.printf("%d %d", l, r);
8
            return ((double)l + r)/2;
9
        }
10
        else {
11
            return helper(nums1, nums2, 0, m-1, 0, n-1, (m+n)/2+1);
12
        }
13
    }
14
    public static int helper(int[] nums1, int []nums2, int s1, int e1, int s2, int e2, int index){
15
        if (s1 > e1){
16
            return nums2[s2 + index - 1];
17
        }
18
        else if (s2 > e2){
19
            return nums1[s1 + index - 1];
20
        }
21
        if (index == 1){
22
            return Math.min(nums1[s1], nums2[s2]);
23
        }
24
        int mid1 = s1 + index / 2 - 1;
25
        int mid2 = s2 + index / 2 - 1;
26
        if (mid1 > e1 ) return helper(nums1, nums2, s1, e1, mid2+1, e2, index - index/2);
27
        else if (mid2 > e2) return helper(nums1, nums2, mid1+1, e1, s2, e2, index - index/2);
28
        if (nums1[mid1] <= nums2[mid2]){
29
            return helper(nums1, nums2, mid1+1, e1, s2, e2, index - index/2);
30
        }
31
        else {
32
            return helper(nums1, nums2, s1, e1, mid2+1, e2, index - index/2);
33
        }
34
    }

Solution 2#

Brute force,相当于merge sort

1
public static double findMedianSortedArrays(int[] nums1, int[] nums2) {
2
        int nums3[] = new int [nums1.length + nums2.length];
3
        int i = 0, j = 0, z = 0;
4
        for (; i < nums1.length && j < nums2.length;){
5
            if (nums1[i] <= nums2[j]){
6
                nums3[z++] = nums1[i++];
7
            }
8
            else nums3[z++] = nums2[j++];
9
        }
10
        for (;i < nums1.length; ++i){
11
            nums3[z++] = nums1[i];
12
        }
13
        for (;j < nums2.length; ++j){
14
            nums3[z++] = nums2[j];
15
        }
16

17
        if (nums3.length % 2 == 0){
18
            return (double)(nums3[nums3.length / 2 - 1] + nums3[nums3.length / 2]) / 2;
19
        }
20
        else return (double)nums3[nums3.length / 2];
21
    }