There are two sorted arrays A and B 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)).

Show Tags

题意：求两个有序数组的组成一个新的数组的中位数

思路：题目转换为求第k大的数。假设总个数是奇数的话，就是求第中间的数了，假设是偶数的话。就是找到两个中间的，求平均数。

求第k大的数：首先如果我们求的是两个数组A和B中第k个数。为了我们每次都能折半查找，我们比較A[k/2]和B[k/2]这两个数，如果A[k/2-1]<B[k/2-1]的话。说明的是A数组的前k/2个数字都是在最后数组的前k个中，那么就能够裁掉一点了，依次类推

class Solution {public:    double findMedianSortedArrays(int A[], int m, int B[], int n) {        int size = m + n;        int k = (m + n + 1) / 2;        if (size & 1)            return findKth(A, m, B, n, k);        else return (findKth(A, m, B, n, k) + findKth(A, m, B, n, k+1)) / 2;    }        double findKth(int A[], int m, int B[], int n, int k) {        if (m > n)            return findKth(B, n, A, m, k);        if (m == 0)            return B[k - 1];        if (k == 1)            return A[0] < B[0] ? A[0] : B[0];                int index = k / 2;          int left = index < m ?

index : m; int right = k - left; if (A[left - 1] < B[right - 1]) return findKth(A + left, m - left, B, n, right); else if (A[left - 1] > B[right - 1]) return findKth(A, m, B + right, n - right, left); else return A[left - 1]; } };

版权声明：本文博客原创文章，博客，未经同意，不得转载。