O(log(m+n)) in Python


  • 0
    A
    def findMedianSortedArrays(self, nums1, nums2):
            """
            :type nums1: List[int]
            :type nums2: List[int]
            :rtype: float
            """
            m_len, n_len, i, j = len(nums1), len(nums2), 0, 0
            # 似乎可以不用判断
            if m_len + n_len == 0: raise ValueError
            # midian代表中间第几个是中间数,flag表示本次样例时是否是偶数个,因为偶数个的时候还要加上midian之前的数
            # 比如num = [1, 2, 3, 4]  此时midian是 2,返回的结果应该是float(num[midian] + num[midian-1]) / 2
            # midian represents the index half of the two list, flag represents the count of the two list is even
            midian, flag = (m_len + n_len) >> 1, (m_len + n_len + 1) % 2
            # 表示前一个数,免得在后面还要计算一次,直接在遍历的时候记录下来
            # record the number before midian, avoid calculating again
            midian_front_num = 0
            while i < m_len and j < n_len:
                # 找到中间数了
                # Perfect! The midian is found
                if i + j == midian:
                    midian_num = min(nums1[i], nums2[j])
                    # 这里要注意是不是奇数个
                    # Be careful! Is the count of two list even?
                    if flag: return float(midian_num + midian_front_num) / 2.0
                    else: return midian_num
                # 让增加的始终保持是nums1, 方便返回结果
                # to keep nums1 represents index increased
                if nums1[i] < nums2[j]:
                    i, j, nums1, nums2, m_len, n_len, midian_front_num = i + 1, j, nums1, nums2, m_len, n_len, nums1[i]
                else:
                    # 
                    i, j, nums1, nums2, m_len, n_len, midian_front_num = j + 1, i, nums2, nums1, n_len, m_len, nums2[j]
            # 到这肯定是没找到的
            # Unforunately, we failed to find after executing the code above
            # 把还有多余数的list放到nums1中,我比较讨厌做很多判断,这样就可以减少判断。
            # put the reset data in nums1, to decrease judgements
            if j < n_len: i, j, nums1, nums2, m_len, n_len = j, i, nums2, nums1, n_len, m_len
            # 同上
            # the same as above
            if flag:
                # 如果恰好i+j == midian,如果恰好又是偶数个的话,
                if i+j == midian:
                    midian_front_num = nums2[n_len-1]
                    # 再恰好是i是0的话,你就掉到坑里去了
                    if i == 0:
                        midian_front_num = max(nums1[midian-j-1], midian_front_num)
                    # 这里之前没有加float,=。= 在[1, 2], [3, 4]的样例中,本机运行的2.5  oj运行的是2  不知道为什么没有转换成浮点数
                    # 上面的坑没有掉进去,这里掉进去了
                    # you should convert the result to float
                    return float(nums1[midian-j] + midian_front_num) / 2.0
                else:
                    return float(nums1[midian-j] + nums1[midian-j-1]) / 2.0
            # 这次是真的没坑了
            return nums1[midian-j]
    

Log in to reply
 

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