算法练习2

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

解题思路

题目大意是寻找两个有序数组的中位数。这是一个比较经典的算法题了，首先比较直观的解法就是合并数组然后求中位数。合并再排序可以优化以下，先计算长度，合并一半中位数就出来了。这样减少了一半的时间。

其实根据上面的思路我们不难看出，求中位数就是查找序列中第k大的数(第k-1和k大的数，k是len/2)。那么二分查找是一个很好的选择。这个思路有一个难点就是双数组的奇偶长度不好处理，我借鉴了Manacher算法的那个骚操作，无论数组长度奇偶，通过插入特殊字符统统转换成奇数长度。我们先定义以下，将一个数组切成两个，左边最大为L，右边最小为R。则当L1>R2时，L1减小，R2增大，当L2>R1时，L2减小，R1增大(这里面有个割的概念在此不赘述)。上面那个加特殊字符的操作还有一个奇妙的地方，每个位置除以2得到原来元素的位置，同时无论是切在特殊符号后面还是切在数字后面L=(k-1)/2;R=(k)/2; (k为切的位置)若L==R，则L是切的数字原来的位置，反之，L是特殊字符前的数字之前的位置，R是特殊字符后的数字之前的位置。

代码

//合并再计算中位数
public class Solution {
    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        int l1 = nums1.length;
        int l2 = nums2.length;
        int l = l1 + l2;
        int[] res = new int[l/2 + 1];
        int cur1 = 0, cur2 = 0;
        for (int i = 0; i < l/2 + 1; i++) {
            int a = cur1 < l1 ? nums1[cur1] : Integer.MAX_VALUE;
            int b = cur2 < l2 ? nums2[cur2] : Integer.MAX_VALUE;
            if (a < b) {
                res[i] = a;
                cur1++;
            } else {
                res[i] = b;
                cur2++;
            }
        }
        if (l % 2 != 0) return res[l / 2];
        else return (res[l / 2 - 1] + res[l / 2]) / 2.0;
    }
}

//分治法
public class Solution {
    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        if(nums1.length == 0)
            return MedofArray(nums2);
        if(nums2.length == 0)
            return MedofArray(nums1);
        int n = nums1.length;
        int m = nums2.length;
        if(n > m)   //保证数组1一定最短
            return findMedianSortedArrays(nums2,nums1);
        int L1 = 0, L2 = 0, R1 = 0, R2 = 0, c1, c2, lo = 0, hi = 2 * n;  //虚拟加了'#'所以数组1是2*n+1长度
        while(lo <= hi) {//二分
            c1 = (lo + hi) / 2;  //c1是二分的结果
            c2 = m + n - c1;
            //判断越界
            L1 = (c1 == 0) ? Integer.MIN_VALUE : nums1[(c1 - 1) / 2];//中位数在数组1中
            R1 = (c1 == 2 * n) ? Integer.MAX_VALUE : nums1[c1 / 2];//中位数在数组1中
            L2 = (c2 == 0) ? Integer.MIN_VALUE : nums2[(c2 - 1) / 2];//中位数在数组2中
            R2 = (c2 == 2 * m) ? Integer.MAX_VALUE : nums2[c2 / 2];//中位数在数组1中
            if(L1 > R2) hi = c1 - 1;
            else if(L2 > R1) lo = c1 + 1;
            else break;
        }
        return (Math.max(L1,L2) + Math.min(R1,R2)) / 2.0;
    }
    private double MedofArray(int[] nums) {
        if(nums.length == 0)    return - 1;
        return (nums[nums.length / 2] + nums[(nums.length-1) / 2]) / 2.0;
    }
}