1. 题目

004-Median_of_two_sorted_arrays

2. 算法

http://www.acmerblog.com/leetcode-median-of-two-sorted-arrays-5330.html

http://usagi.cc/article/index.php?aid=10006

• 要求复杂度O(nlg(n+m))

3. 代码

#include<iostream>

#include<vector>

#include<algorithm>

#include<map>

#include <stack>

#include<unordered_map>

#include <utility>

using namespace std;

class Solution {

public:

    double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {

        int total = nums1.size() + nums2.size();

        if (total & 0x1 ) {

            return findKth(nums1, nums2, total / 2 + 1);

        } else {

            vector<int>a ,b;

            a.assign(nums1.begin(),nums1.end());

            b.assign(nums2.begin(),nums2.end());

            return (findKth(nums1,  nums2,  total / 2) + findKth(a,b, total / 2 + 1)) / 2;

        }

    }

    double findKth(vector<int> &A,  vector<int> &B,  int k) {

        int m=A.size();

        int n=B.size();

        if (m > n) return findKth(B,A,k);

        if (m == 0) return B[k - 1];

        if (k == 1) return min(A[0], B[0]);

        int pa = min(k / 2, m), pb = k-pa;

        if (A[pa - 1] < B[pb - 1]){

            A.erase(A.begin(),A.begin()+pa);

            return findKth(A,B,k-pa);

        }

        else if (A[pa - 1] > B[pb - 1]) {

            B.erase(B.begin(),B.begin()+pb);

            return findKth(A,B,k-pb);

        }

        else {

            return A[pa - 1];

        }

    }

};

int main(){

    int a[]={1,2,3,4};

    int b[]={5,6,7,8};

    vector<int> A(&a[0],&a[4]);

    vector<int> B(&b[0],&b[4]);

    Solution solution;

    double result = solution.findMedianSortedArrays(A, B);

    cout<<result<<endl;

}