LeetCode

Median of Two Sorted Arrays

2013.12.1 19:29

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)).

Solution:

　　Given two sorted array, find out the median of all elements. My solution is straightforward, merge two arrays and return the median.

　　Time complexity is O(m + n), space complexity O(m + n) as well. In-place merge is too much trouble, and merging by swapping have some bad case of O(n^2) time compleity. So the direct solution is sometimes a wise solution at all :) 

　　Here is the accepted code.

Accepted code:

// 1RE 1AC
class Solution {
public:
    double findMedianSortedArrays(int A[], int m, int B[], int n) {
        // IMPORTANT: Please reset any member data you declared, as
        // the same Solution instance will be reused for each test case.
        merge(A, m, B, n);
        if((m + n) % 2 == 1){
            return C[(m + n - 1) / 2];
        }else{
            return (C[(m + n) / 2 - 1] + C[(m + n) / 2]) / 2.0;
        }
    }
private:
    vector<int> C;
    
    void merge(int A[], int m, int B[], int n) {
        C.clear();
        
        int i, j;
        
        i = j = 0; // Bugged here, omitted this sentence
        while(i < m && j < n){
            if(A[i] <= B[j]){
                C.push_back(A[i++]);
            }else{
                C.push_back(B[j++]);
            }
        }
        
        while(i < m){
            C.push_back(A[i++]);
        }
        
        while(j < n){
            C.push_back(B[j++]);
        }
    }
};