A dumb accepted C++ O(log(m + n)) code. Need some help for shortening. Thanks!


  • 1
    L
    class Solution {
    
    private:
    double findMedian(vector<int>& nums){
        int tag = nums.size() % 2;
        if(tag == 0){
            return double((nums[nums.size() / 2] + nums[nums.size() / 2 - 1])) / 2;
        }
        else{
            return nums[nums.size() / 2];
        }
    }
    
    int Judge(vector<int>& nums1, vector<int>& nums2){
        int tag = nums2.size() % 2;
        if(tag == 0){
            if(nums1[0] >= nums2[nums2.size() / 2 - 1] && nums1[1] <= nums2[nums2.size() / 2]){
                return 1;
            }
            else
                return 0;
        }
        else{
            if(nums1[0] <= nums2[nums2.size() / 2] && nums1[1] >= nums2[nums2.size() / 2]){
                return 1;
            }
            else
                return 0;
        }
        
    }
    
    double findMedian_1(vector<int>& nums1, vector<int>& nums2){
        int tag = nums2.size() % 2;
        int m = nums1[0];
        if(tag == 0){
            if(m <= nums2[nums2.size() / 2] && nums2[nums2.size() / 2 - 1] <= m){
                return m;
            }
            else if(m < nums2[nums2.size() / 2 - 1]){
                return nums2[nums2.size() / 2 - 1];
            }
            else{
                return nums2[nums2.size() / 2];
            }
            
        }
        else{
            if(nums2.size() == 1){
                return double(nums1[0] + nums2[0]) / 2;
            }
            else if(m <= nums2[nums2.size() / 2 + 1] && nums2[nums2.size() / 2 - 1] <= m){
                return double(nums2[nums2.size() / 2] + m) / 2;
            }
            else if(m < nums2[nums2.size() / 2 - 1]){
                return double(nums2[nums2.size() / 2 - 1] + nums2[nums2.size() / 2]) / 2;
            }
            else{
                return double(nums2[nums2.size() / 2] + nums2[nums2.size() / 2 + 1]) / 2;
            }
        }
        
    }
    
    int min(int num1, int num2){
        if(num1 < num2){
            return num1;
        }
        else{
            return num2;
        }
    }
    
    public:
    double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
        
        int size = nums1.size() + nums2.size();
        if(nums1.size() == 0){
            return findMedian(nums2);
        }
        if(nums2.size() == 0){
            return findMedian(nums1);
        }
        
        do{
            if(nums1.size() == 2 && nums2.size() == 2){
                if(Judge(nums1, nums2)){
                    return double(nums1[0] + nums1[1]) / 2;
                } 
                if(Judge(nums2, nums1)){
                    return double(nums2[0] + nums2[1]) / 2;
                }
            }
            
            if(nums1.size() == 2 && nums2.size() != 1){
                int temp = Judge(nums1, nums2);
                if(temp == 1){
                    if(nums2.size() % 2 == 0){
                        return double(nums1[0] + nums1[1]) / 2;
                    }
                    else{
                        return findMedian(nums2);
                    }
                }
                else{
                    if(findMedian(nums1) == findMedian(nums2)){
                        return findMedian(nums1);
                    }
                    else if(findMedian(nums1) > findMedian(nums2)){
                        nums1.erase(nums1.begin() + 1);
                        nums2.erase(nums2.begin());
                    }
                    else{
                        nums1.erase(nums1.begin());
                        nums2.erase(nums2.begin() + nums2.size() - 1);
                    }
                }
                
            }
            if(nums2.size() == 2 && nums1.size() != 1){
                
                int temp = Judge(nums2, nums1);
                if(temp == 1){
                    if(nums1.size() % 2 == 0){
                        return double(nums2[0] + nums2[1]) / 2;
                    }
                    else{
                        return findMedian(nums1);
                    }
                }
                else{
                    if(findMedian(nums2) == findMedian(nums1)){
                        return findMedian(nums1);
                    }
                    else if(findMedian(nums2) > findMedian(nums1)){
    
                        nums2.erase(nums2.begin() + 1);
                        nums1.erase(nums1.begin());
                    }
                    else{
                        nums2.erase(nums2.begin());
                        nums1.erase(nums1.begin() + nums1.size() - 1);
                    }
                }
                
            }
            if(nums1.size() == 1){
                return findMedian_1(nums1, nums2);
            }
            if(nums2.size() == 1){
                return findMedian_1(nums2, nums1);
            }
            
            double med1 = findMedian(nums1);
            double med2 = findMedian(nums2);
            int tag1 = nums1.size() % 2;
            int tag2 = nums2.size() % 2;
            int cut1, cut2;
            
            if(tag1 == 0){
                cut1 = nums1.size() / 2 - 1;
            }
            else{
                cut1 = nums1.size() / 2;
            }
            if(tag2 == 0){
                cut2 = nums2.size() / 2 - 1;
            }
            else{
                cut2 = nums2.size() / 2;
            }
            int cut = min(cut1, cut2);
          
            if(med1 == med2){
                return findMedian(nums1);
            }
            else if(med1 > med2){
                nums1.erase(nums1.begin() + nums1.size() - cut, nums1.begin() + nums1.size());
                nums2.erase(nums2.begin(), nums2.begin() + cut);
            }
            else{
                nums2.erase(nums2.begin() + nums2.size() - cut, nums2.begin() + nums2.size());
                nums1.erase(nums1.begin(), nums1.begin() + cut); 
            }
            
            
            
            
            
        }while(1);
        
        
        
        
        
       return 0; 
    }
    

    };


  • 0
    G

    you can check mine, it is short, enjoy~

    my solution and analysis on github


Log in to reply
 

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