4.Median of Two Sorted Arrays

找到两个已排序数列的中位数

给出两个已排序的数列 $nums1$ 和 $nums2$ ，两个数列长度分别为 $m$ 和 $n$ ，返回这两个数列的中位数。总体的时间复杂度应该是 $O(log(m+n))$ 。

例 1：

输入：nums1 = [1,3], nums2 = [2]
输出：2.00000
解析：合并后数列为 [1,2,3]，中位数为 2。

例 2：

输入：nums1 = [1,2], nums2 = [3,4]
输出：2.50000
解析：合并后数列为 [1,2,3,4]，中位数为（2 + 3）/ 2 = 2.5。

约束条件：

\begin{aligned} nums1.length == m&\\ nums2.length == n&\\ 0 <= m <= 1000&\\ 0 <= n <= 1000&\\ 1 <= m + n <= 2000&\\ -10^6 <= nums1[i], nums2[i] <= 10^6& \end{aligned}

一开始，写的代码比较直观，使用递归方法，一直移动边界，直到可以直接计算中位数

 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
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
double findMedianSortedArrays(int *nums1, int nums1Size, int *nums2, int nums2Size)
{

#define get_cn(s, n)                                \
    do                                              \
    {                                               \
        if (n % 2 == 0)                             \
        {                                           \
            return (s[n / 2] + s[n / 2 - 1]) / 2.0; \
        }                                           \
        else                                        \
        {                                           \
            return s[n / 2];                        \
        }                                           \
    } while (0);

    if (nums1Size == 0)
    {
        get_cn(nums2, nums2Size);
    }
    else if (nums2Size == 0)
    {
        get_cn(nums1, nums1Size);
    }
    else if (nums1Size == 1 && nums2Size == 1)
    {
        return (nums1[0] + nums2[0]) / 2.;
    }

    if (nums1[0] >= nums2[0])
    {
        nums2++;
        nums2Size--;
        if (nums2Size == 0)
        {
            nums1Size--;
            get_cn(nums1,nums1Size);
        }
        else if (nums1[nums1Size - 1] >= nums2[nums2Size - 1])
        {
            nums1Size--;
        }
        else
        {
            nums2Size--;
        }
    }
    else
    {
        nums1++;
        nums1Size--;
        if (nums1Size == 0)
        {
            nums2Size--;
            get_cn(nums2,nums2Size);
        }
        else if (nums1[nums1Size - 1] >= nums2[nums2Size - 1])
        {
            nums1Size--;
        }
        else
        {
            nums2Size--;
        }
    }

    return findMedianSortedArrays(nums1, nums1Size, nums2, nums2Size);
}
C

后来把递归改为迭代，移动边界，直到满足计算条件

 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
37
38
39
40
41
42
43
44
45
46
47
48
double findMedianSortedArrays(int *nums1, int nums1Size, int *nums2, int nums2Size)
{

#define get_cn(s, n)                                \
    do                                              \
    {                                               \
        if (n % 2 == 0)                             \
        {                                           \
            return (s[n / 2] + s[n / 2 - 1]) / 2.0; \
        }                                           \
        else                                        \
        {                                           \
            return s[n / 2];                        \
        }                                           \
    } while (0);

    while (nums1Size >= 1 && nums2Size >= 1 && nums1Size + nums2Size > 2)
    {
        if (nums1[0] >= nums2[0])
        {
            nums2++;
            nums2Size--;
        }
        else
        {
            nums1++;
            nums1Size--;
        }
        if (nums1[nums1Size - 1] >= nums2[nums2Size - 1])
        {
            nums1Size--;
        }
        else
        {
            nums2Size--;
        }
    }

    if (nums1Size==0){
        get_cn(nums2,nums2Size);
    }else if (nums2Size==0){
        get_cn(nums1,nums1Size);
    }else{
        return (nums1[0]+nums2[0])/2.0;
    }


}
C

提交截图(提交时，非现在状态)

完整信息点击此连接查看

上面的算法效率并不高，实际上分析下，其时间复杂度其实是 $O(m+n)$ 。题解要求的复杂度是 $O(log(m+n))$，也即要求不能逐个寻找，应该有某种类似于快速梯度下降的法子，这里实际上二分搜索应该可以考虑下。

二分搜索的递归解法如下:

 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
37
38
39
40
41
42
43
44
45
46
47
48
49
50
double findKthSortedArrays(int *nums1, int nums1Size, int *nums2, int nums2Size, int kth)
{
    if (nums1Size == 0)
    {
        return nums2[kth - 1];
    }
    if (nums2Size == 0)
    {
        return nums1[kth - 1];
    }
    if (kth == 1)
    {
        return nums2[0] > nums1[0] ? nums1[0] : nums2[0];
    }
    int kth_left_half = kth / 2;
    int kth_right_half = kth / 2;

    if (nums1Size < kth_left_half)
    {
        kth_left_half = nums1Size;
    }
    if (nums2Size < kth_right_half)
    {
        kth_right_half = nums2Size;
    }

    if (nums1[kth_left_half - 1] <= nums2[kth_right_half - 1])
    {
        nums1 += kth_left_half;
        nums1Size -= kth_left_half;
        kth -= kth_left_half;
    }
    else if (nums1[kth_left_half - 1] > nums2[kth_right_half - 1])
    {
        nums2 += kth_right_half;
        nums2Size -= kth_right_half;
        kth -= kth_right_half;
    }
    return findKthSortedArrays(nums1, nums1Size, nums2, nums2Size, kth);
}

double findMedianSortedArrays(int *nums1, int nums1Size, int *nums2, int nums2Size)
{
    // find (nums1Size+nums2Size)/2 th num
    int left_kth = (nums1Size+nums2Size+1)/2;
    int right_kth = (nums1Size+nums2Size+2)/2;

    return (findKthSortedArrays(nums1,nums1Size,nums2,nums2Size,left_kth)+
    findKthSortedArrays(nums1,nums1Size,nums2,nums2Size,right_kth))/2.0;
}
C

提交截图(提交时，非现在状态)

完整信息点击此连接查看

找到两个已排序数列的中位数

提交截图(提交时，非现在状态)

提交截图(提交时，非现在状态)

未完待续。。。解递归方法