40ms o(m+n) Solution?


  • 0
    M

    Accepted with 40ms.

    I think my Solution will work in o(m+n), But I can't sure. So I can't sure my solution is right. (whether in O(log (m+n)))

    Can u tell me my solution complexity?

    class Solution {
    public:
        double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
            int n1 = -1, n2 = -1, val1 = 0, val2 = 0;
            int count = (nums1.size() + nums2.size()) / 2;
            while(count--){
                val1 = ((n1+1 < nums1.size()) && (n2+1 < nums2.size())) ? ((nums1[n1+1] < nums2[n2+1]) ? nums1[++n1] : nums2[++n2]) : ((n1+1 < nums1.size()) ? nums1[++n1] : nums2[++n2]);
            }
            val2 = ((n1+1 < nums1.size()) && (n2+1 < nums2.size())) ? ((nums1[n1+1] < nums2[n2+1]) ? nums1[++n1] : nums2[++n2]) : ((n1+1 <nums1.size()) ? nums1[++n1] : nums2[++n2]);
            return ((nums1.size() + nums2.size()) % 2 == 1) ? val2 : (val1+val2)/2.0;
        }
    };

  • 0
    A

    didnt look at how it works, but complexity is O(m+n) since the loop runs (m+n) times and everything else is O(1)


  • 0
    M

    Ok, thanks. just confirm my solution complexity is good


Log in to reply
 

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