Leetcode -- Median of Two Sorted Arrays

Solution 03/30/2014

class Solution {

public:

    double findMedianSortedArrays(int A[], int m, int B[], int n) {

        std::vector merged;

        mergeTwoSortedArrays(merged, A, m , B, n);

        double ret;

        if(merged.size() % 2) {

            ret = merged[(m + n) / 2];

        } else {

            ret = ((double)merged[(m + n) /2 - 1] + (double) merged[(m + n)/2]) / 2;

        }

        return ret;

    }

   

    void mergeTwoSortedArrays(std::vector& merged, int A[], int m, int B[], int n) {

        size_t iA = 0, iB = 0;

       

        while(iA < m || iB < n) {

            if(iA < m && iB < n) {

                int smaller = A[iA] <= B[iB] ? A[iA++] : B[iB++];

                merged.emplace_back(smaller);

            }

           

            if(iA < m && iB >= n) {

                merged.emplace_back(A[iA++]);

            }

           

            if(iA >= m && iB < n) {

                merged.emplace_back(B[iB++]);

            }

        }

    }

};