C++, very simple O(n) solution, with explanation


  • -1
    D

    Not sure why this is a "hard" problem here. I found many "medium" ones harder. It is very easy if you don't think too much about statistics and use common sense. We simply start "taking" elements from both arrays, starting at the beginning. At every step we take the next element from one or the other array, whichever is smaller. When we've taken half of the total number of elements, we're at the middle of the combined array and can return the median. The code below is quick-and-dirty, but it is accepted solution and faster than 84% of other solutions:

    class Solution {
    public:
        double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
            int i1 = 0, i2 = 0;
            int totalCount = nums1.size() + nums2.size();
            if (totalCount < 2)
                return nums1.size() ? nums1[0] : nums2[0];
            double prevVal, nextVal;
            while (i1 < nums1.size() || i2 < nums2.size()) {
                prevVal = nextVal;
                if (i1 < nums1.size() && (i2 >= nums2.size() || nums2[i2] > nums1[i1])) {
                    nextVal = nums1[i1];
                    i1++;
                }
                else if (i2 < nums2.size()) {
                    nextVal = nums2[i2];
                    i2++;
                }
                if (i1 + i2 > (totalCount) / 2)
                    return totalCount % 2 ? nextVal : (nextVal + prevVal) / 2;
            }
        }
    };
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.