can somebody help me to figure out what's the complexity of my algorithm


  • 0
    M
    #include <vector>
    #include <limits>
    #include <cmath>
    using namespace std;
    // 1 2 3 4
    // 5 6 7 8
    
    // 1 2 3 3 4
    // 4 5 6 7 8
    
    // 7
    // 2 3 4 5 6 8 8 9 10 11
    
    class Solution {
    public:
        double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2){
          auto len1 = nums1.size();
          auto len2 = nums2.size();
    
          auto two_median = false;
          auto total = len1 + len2;
          if(total%2 == 0) two_median = true;
    
          auto imin = std::numeric_limits<int>::min();
          auto imax = std::numeric_limits<int>::max();
    
          nums1.insert(nums1.begin(), imin); nums1.push_back(imax);
          nums2.insert(nums2.begin(), imin); nums2.push_back(imax);
    
          auto start1 =0, start2 =0;
          if(len1<len2){
            start1 = len1/2;
            start2 = (int)(std::ceil(((double)total)/2)) - start1;
          }
          else{
            start2 = len2/2;
            start1 = (int)(std::ceil(((double)total)/2)) - start2;
          }
        
          while(true){
            if(nums2[start2+1] < nums1[start1]){
              start2 = start2 + 1;
              start1 = start1 - 1;
            }
            else if(nums1[start1+1] < nums2[start2]){
              start1 = start1 + 1;
              start2 = start2 - 1;
            }
            else{
              break;
            }
          }
    
          if(two_median){
            double m1 = 0, m2 = 0;
            m1 = std::max(nums1[start1], nums2[start2]);
            m2 = std::min(nums1[start1+1], nums2[start2+1]);
            return (m1+m2)/2;
          }
          else{
            return std::max(nums1[start1], nums2[start2]);
          }
        }
    };
    

Log in to reply
 

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