Algorithm: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

Level: Hard

解题思路与状态

问题分析

已知条件
两个排序数组，数组num1，元素个数为m；数组num2，元素个数为n；
问题
找到num1和num2的中位数
约束
算法的运行最坏时间为 O(log(m+n))

解题思路

归并排序法

如果没有时间约束，就可以使用归并排序，若排序后的结果为nums3,元素个数为k=m+n;最终将问题转化为：
求数组nums3的中位数。

若k为奇数，直接为nums3[k/2];
若k为偶数，则为(nums3[k/2]+nums3[k/2-1])/2；

此解法的时间复杂度为O(m+n),主要是归并排序上；空间复杂度为O(m+n)，用于暂存归并排序后的结果。
具体的代码如下：

// find the median of a sorted arrray
private double findMedianSortedSignleArray(int[] nums) {
    if (null == nums || 0 == nums.length) {
        throw new  IllegalArgumentException("sorted arrays are illegal.");
    }
    int len = nums.length;
    if (0 == len % 2) {
        return (nums[len/2] + nums[len/2 - 1]) / 2.0;
    }
    return nums[len/2];
}

public double findMedianSortedArrays(int[] nums1, int[] nums2) {
    if (null == nums1 || 0 == nums1.length) {
        return findMedianSortedSignleArray(nums2);
    }
    if (null == nums2 || 0 == nums2.length) {
        return findMedianSortedSignleArray(nums1);
    }
    
    // using merge sort 
    int n = nums1.length;
    int m = nums2.length;
    
    int[] mergeNum = new int[n + m];
    
    int i = 0;
    int j = 0;
    int k = 0;
    while (i < n & j < m) {
        if (nums1[i] > nums2[j]) {
            mergeNum[k++] = nums2[j++];
        } else {
            mergeNum[k++] = nums1[i++];
        }
    }
    while (i < n) {
        mergeNum[k++] = nums1[i++];
    }
    while (j < m) {
        mergeNum[k++] = nums2[j++];
    }
    
    return findMedianSortedSignleArray(mergeNum);
}

递归算法

目前递归算法还未写出来，断断续续思考使用递归的想法有几天了，一直未果。现在留着不写，后续解决
之后在补上。

总结

对于使用递归算法解决此问题没能解决，内心是十分痛苦的。目前的思路是能否借助于二分查找算法解决，
最为关键的是递归结束的条件是什么。

Contents