LeetCode.4. Median of Two Sorted Arrays

leetcode

题目要求

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

思路

整体思路是：

假设有一段数据，需要找到符合要求的那个元素
1. 把数据分成两半. 有可能不是长度相等的两半
2. 扔掉肯定不符合要求的那一半
3. 回到第1步

这里面算法复杂度的关键就是在第1步里面拆分成两半的处理。
如果拆分的过程中是需要遍历每个元素。那么整个数据的处理复杂度为O(n)。
这里典型的思路就是寻找第k小的数。

如果拆分的过程中不需要遍历每个元素，可以通过快速的手段即可把整个数组
拆分成两部分，那么整个算法的复杂度就是O(lgn)。这里面典型的就是二分查找。

寻找第k小的数

首先介绍一下寻找第k小数的思路。这个思路与快排非常相似。

1. 找一个数:一般取数组的中间元素。
2. 通过这个数把数组切分成两半。左边数组a1[]比这个元素小，右边数组a2[]比这个元素大。
3. 如果k <= len(a1[]), 那么k肯定只能在a1[]里面找。用a1[]来进行递归->回第1步
4. 如果k > len(a1[])，那么k肯定只能在a2[]里面找。用a2[]来进行递归->回第1步

详细代码如下：

// 找到第k小的数，这里可以在POJ:
// http://poj.org/problem?id=2388
// 只不过POJ 2388是用来寻找一个有序数组中间(n/2)的那个元素。
// 利用kth变种之后，就是寻找第n/2+1小的元素。
int kth(int *a, int b, int e, int k) {
    if ((b+1) == e) return a[b];
    int i = b - 1;
    int j = e;
    int x = a[b+((e-b)>>1)];
    while (i < j) {
        while (a[++i]<x); while (a[--j] > x);
        if (i < j) {int t = a[i]; a[i] = a[j]; a[j] = t;}
    }
    if (k <= (i-b)) return kth(a, b, i, k);
    else return kth(a, i, e, k-(i-b));
}

有了这段代码之后，也可以用来寻找第k大的元素。
LeetCode 寻找第k大的元素

// 第k小与第n大的关系是
// 第1小对应于第size大
// 第size小对应于第1大
// 所以两者k+n == size+1
int findKthLargest(int* nums, int numsSize, int k) {
    return kth(nums, 0, numsSize, numsSize + 1 - k);
}

即然讲到这里，也可以把快速排序的代码整理出来。快排的题目
LeetCode排序

void quick_sort(int *a, int b, int e) {
    if (b >= e || (b+1) == e) return;
    int i = b -1;
    int j = e;
    int x = a[b+((e-b)>>1)];
    while (i < j) {
        while (a[++i]<x); while (a[--j] > x);
        if (i < j) {int t = a[i]; a[i] = a[j]; a[j] = t;}
    }
    quick_sort(a, b, i);
    quick_sort(a, i, e);
}
void sortColors(int* nums, int numsSize) {
    quick_sort(nums, 0, numsSize);
}

注意快排有个点需要注意

void quick_sort(int *a, int b, int e) {
    if (b >= e || (b+1) == e) return;
    int i = b -1;
    int j = e;
    int x = a[b+((e-b)>>1)];
    while (i < j) {
        while (a[++i]<x); while (a[--j] > x);
        if (i < j) {int t = a[i]; a[i] = a[j]; a[j] = t;}
    }
    // Q: 这里i和j是什么关系？
    //    为什么后面在分界的时候，是以来进行分界的?
    quick_sort(a, b, i);
    quick_sort(a, i, e);
}

当while (i < j)结束之后，i与j的关系有两种

1. i == j
2. i > j

当i == j的时候，直接用

quick_sort(a, b, i);
quick_sort(a, i, e);

来排序后面的两个数组是没有问题的。

但是，当j!=i此时必然有j<i且j+1 == i
那么如果再用

quick_sort(a, b, j);
quick_sort(a, i, e);

来排序就会出错。因为a[j]这个时候没有被计入到排序里面。
如果要把a[j]放到前面的数组里面一起排序。就应当把代码写成

quick_sort(a, b, j+1);
quick_sort(a, i, e);

而此时j+1 == i。所以逻辑统一之后就是

quick_sort(a, b, i);
quick_sort(a, i, e);

二分搜索

int *binary_search(int *b, int *e, int v) {
    int *m = NULL;
    while (b < e) {
        m = b + ((e-b)>>1);
        if (*m == v) return m;
        if (*m > v) e = m;
        else b = m + 1;
    }
    return NULL;
}

解法

回到题目本身，由于两个数组都是已经排好序的。找两个数组最中间的那个数。

由于是两个数组，在讨论的时候，可以认为是在从这两个有序数组中找第k小的元素。
如果数组长度为奇数，那么就是第(n/2)+1小的元素。如果长度为偶数，那么就是取
第(n/2)小和第(n/2)+1小的平均数。那么主函数可以写成如下样子。

double findMedianSortedArrays(int* nums1, int nums1Size, int* nums2, int nums2Size) {
    int len = nums1Size + nums2Size;
    int midPos = len >> 1;
    /*
     * 如果是奇数，找最中间的元素
     * 比如: 1 + 2 == 3, 3 >> 1 == 1 == midPos; [0,1=midPos,2]也就是要找第midPos+1个
     * 如果是偶数，这里找到是前面一个元素
     * 比如： 2+2=4, 4>>1 == 2 == midPos; [0,1,2,3] =>第[1,2=midPos,3,4]个, 
     * 用midPos+1则找到了后面一个
     */
    double a = findKthItem(nums1, nums1 + nums1Size, nums2, nums2 + nums2Size, midPos + 1);
    if (!(len & 0x01)) {
        /*长度为偶数*/
        double b = findKthItem(nums1, nums1 + nums1Size, nums2, nums2 + nums2Size, midPos);
        return (a + b) / 2;
    }
    return a;
}

接下来就是看findKthItem的实现了。

1. 给定两个数组a[], b[], 从数组a[]中找到中位数M。把a[], b[]切分成两部分。
   a1[] 小于M, a2[]大于等于M
   b1[] 小于M, b2[]大于等于M
   两个数组相当于被切分成了两个group.
   groupA = {a1[], b1[]}
   groupB = {a2[], b2[]}
2. 如果k大于len(groupA)，那么要找的元素肯定在groupB. 此时k -= len(groupA)
   如果k小于等于len(groupA)，那么要找到的元素肯定在groupA.
3. 回步骤1

在进行第一步的时候，可以直接找最长的那个数组中位数。因为
最差的情况下，可以把最长数组的一半扔掉。如果是取最短的数组的中位数。
那么最差情况下，只能扔到最短数组的一半。不太划算。所以一开始可以写代码如下：

/*
 * 二分搜索
 * b表示超始位置
 * e表示结束位置
 * 搜索范围[b, e)
 * v表示要找的值
 * 返回元素指针位置，如果没有找到，返回NULL
 * pos指向刚好比v大的位置条件是: 如果: notFound(v) && 且 *b < *v && *v < *(e-1)
 */
int *binarySearch(int *b, int *e, int *v, int **less) {
    int *m = *less = NULL;
    while (b < e) {
        m = b + ((e-b) >> 1);
        if (*m == *v) return m;
        if (*m > *v) e = m;
        else b = m + 1; /*ERROR 1*/
    }
    while (*m < *v && m < e) ++m; /*ERROR3 这里必须要找到刚好大于v的地方*/
    *less = m;
    return NULL;
}
int findKthItem(int *a, int *ae, int *b, int *be, int k) {
    /*
     * 如果b数组长于a数组，交换之
     * 取长数组的中值在短数组的中二分查找，速度更快
     */
    if ((be-b) > (ae-a)) {
        return findKthItem(b, be, a, ae, k);
    }
    assert(0 < k && k <= ((ae-a) + (be-b)));
    assert(((ae-a) + (be-b)) > 0);
    /*如果B数组为空*/
    if (b == be) {
        return a[k-1];
    }
    /*如果A数组为空*/
    if (a == ae) {
        return b[k-1];
    }
    /*如果k == 1*/
    if (1 == k) {
        return a[0] < b[0] ? a[0] : b[0];
    }
    /*如果k刚好是两个数组的长度之和*/
    if (k == ((ae-a) + (be-b))) {
        return *(ae-1) > *(be-1) ? *(ae-1) : *(be-1);
    }
    /*取长数组的中值*/
    int *amid = a + ((ae - a)>>1);
    
    /*在b数组中二分A数组的中间元素*/
    int *less = NULL;
    int *pos = binarySearch(b, be, amid, &less);
    /*
     * 如果amid不存在于B数组中，但是范围落在里面，照样可以把
     * B数组切成两半，这个时候的处理情况与找到的处理是一样的
     * 都是把两个数组切分成了2份。
     */
    if (less && (*b < *amid && *amid < b[be-b-1])) {
        pos = less;
    }
    /*
     * 如果找到A数组的中间元素, 或者
     * pos可以把数组B成功切分成为两半：看pos = less
     */
    if (pos) {
        /*
         * 这个时候数组被切分为两部分
         * 数组A [a, amid), [amid, ae)
         * 数组B [b, pos), [pos, be)
         * 看一下k所在的范围
         */
        /*前半部分的长度*/
        int frontLength = (amid-a) + (pos-b);
        /*与k比较有三种结果*/
        if (frontLength == k) {
            /*
             * 相等:
             * 元素个数刚好与k相等, 只需要取最后一个元素
             */
            int aLast = amid - a - 1;
            int bLast = pos - b - 1;
            return a[aLast] > b[bLast] ? a[aLast] : b[bLast];
        } else if (frontLength > k) {
            /*前面长于k*/
            return findKthItem(a, amid, b, pos, k);
        } else {
            /*前面短于k*/
            return findKthItem(amid, ae, pos, be, k - frontLength);
        }
        /*can't reach here*/
        assert(1 == 0);
    } else {
        /*
         * 找不到，可能有三种情况，
         * 1. 比数组B所有元素小
         * 2. 比数组B所有元素大
         * 3. 介于数组B之间
         */
        if (*amid < *b) {
            /*
             * 情况1：amid < b数组中所有元素
             * [a, amid), [amid, ae)
             *            [b, be)
             */
            int frontLength = amid - a;
            /*也是与k进行比较*/
            if (frontLength == k) {
                /*返回front last元素*/
                int aLast = amid - a - 1;
                return a[aLast];
            } else if (frontLength > k) {
                return a[k-1];
            } else {
                return findKthItem(amid, ae, b, be, k - frontLength);
            }
            
            /*can't reach here*/
            assert(1 == 0);
        } else if (*amid > b[be-b-1]) {
            /*
             * 情况2: amid > b数组中所有元素
             * [a, amid), [amid, ae)
             * [b, be)
             */
            assert(*amid > b[be-b-1]);
            
            int frontLength = amid - a + be - b;
            if (frontLength == k) {
                int aLast = amid - a - 1;
                int bLast = be - b - 1;
                return a[aLast] > b[bLast] ? a[aLast] : b[bLast];
            } else if (frontLength > k) {
                return findKthItem(a, amid, b, be, k);
            } else {
                return amid[k - frontLength - 1];
            }
            /*can't reach here*/
            assert(1 == 0);
        } else {
            /* ERROR2:
             * amid 落在B组数区间中，但是不存在
             * 数组被切分为[a, amid), [amid, ae)
             *           [b, less), [less, be)
             * 这种情况与找到的情况是一样的处理方法，前面已经pos = less
             */
            /*can't reach here*/
            assert(1 == 0);
        }
        
        /*can't reach here*/
        assert(1 == 0);
    }
    
    /*can't reach here*/
    assert(1 == 0);
}

注意各种assert的运用，加强边界判断。最终通过之后，可以把相应的assert去掉。