Share my 44ms solution. Remove useless numbers every iteration.


  • 2
    1. If one of the array is small enough, i.e. less than 5 numbers, then we can build a small array and sort and find the median.
    2. If the two arrays are large enough, it's not possible to do it that way. We need to shrink the two arrays to #1, then we can build the small array and find the median.

    So the question is how to shrink the arrays safely without dropping the critical numbers. For example:

    1. array1={1,3,5,6,8};
    2. array2={-5,-2,2,3,4,5,6,7,8,9, 10, 11};

    Firstly, pick up the two middle numbers. Here, they are 5 and 6. So we know any numbers on the right of 6 in array2 could not contribute to the median value. And any numbers on the left of 5 in array1 could not neither. So the problem becomes find median in:

    1. array1={5,6,8};
    2. array2={2,3,4,5,6,7,8,9};

    Since the size of array1 is less than 4, it's a trivial problem. We can still optimize it a little bit. We can drop the number heading/trailing of array2 since they do not contribute to the median. This way, we can make sure the memory allocated is O(1).

    class Solution {
    public:
    double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
        if(nums1.empty() && nums2.empty()) return 0;
        if(nums1.size()>nums2.size()){
            swap(nums1, nums2);
        }
        return findMedian(nums1, 0, nums1.size(), nums2, 0, nums2.size());
    }
    double findMedian(vector<int>& nums1, int left1, int right1, vector<int>& nums2, int left2, int right2){
        while(true){
            if(right1-left1<=4){
                int size1=right1-left1;
                int size2=right2-left2;
                int diff=max(0,(size2-size1)/2-1);
                vector<int> v(nums2.begin()+left2+diff, nums2.begin()+right2-diff);
                for(int i=left1; i<right1; ++i){
                    v.push_back(nums1[i]);
                }
                sort(v.begin(), v.end());
                int size=v.size();
                return (v[size/2]+v[(size-1)/2])/2.0;
            }
            else{
                int mid1=(left1+right1)/2;
                int mid2=(left2+right2)/2;
                if(nums1[mid1]<nums2[mid2]){//remove left of nums1 and right of nums2
                    int diff=min(mid1-left1, right2-mid2-1);
                    left1+=diff;
                    right2-=diff;
                }
                else{
                    int diff=min(right1-mid1-1, mid2-left2);
                    right1-=diff;
                    left2+=diff;
                }
            }
        }
        return 0;
    }};

Log in to reply
 

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