4. Median of Two Sorted Arrays

最近再刷leetcode,除了链表之外的都用python 实现,贴出一些代码,希望指正.

问题描述:

There are two sorted arrays nums1 and nums2 of size m and n respectively.
Find the median of the two sorted arrays. The overall run time complexity should be O(log (m+n)).
找两个排序好的数组的中位数.

样例输入:

nums1 = [1, 3]
nums2 = [2]

The median is 2.0

nums1 = [1, 2]
nums2 = [3, 4]

The median is (2 + 3)/2 = 2.5

算法思想:

我再这里对两个数组的len和是奇数还是偶数做了分开对待.

1. 如果两个数组len和是奇数.
   对两个数组进行从小到大遍历,同时遍历,当遍历到(length+1)/2输出结果,不过需要注意的是,两个数组的长度不同,可能出现某个遍历完了,某个还没有完的情况,所以在同时遍历完成之后还需要,对没有完成的进行遍历.
2. 对于两个数组的len和是偶数的情况.
   如果两个数组的len和是偶数,那就说明中位数,是最中间两个和的一半,这时就需要对上一个结果进行存储,遍历时,需要找到(length+1)//2的下一个然后和上一个加和求二分之一.

代码写的比较臭

class Solution(object):
    def findMedianSortedArrays(self, nums1, nums2):
        """
        :type nums1: List[int]
        :type nums2: List[int]
        :rtype: float
        """
        m = len(nums1)
        n = len(nums2)
        median = (m + n + 1) / 2

        # print(median)
        def find_int(nums1, nums2, tar):
            # print("find_int")
            # print(nums1, nums2, tar)
            flag = 0
            tmp = -1
            M = N = 0
            while m > M and n > N:
                if flag == tar:
                    return tmp
                if nums1[M] < nums2[N]:
                    tmp = nums1[M]
                    M = M + 1
                    flag = flag + 1
                else:
                    tmp = nums2[N]
                    N = N + 1
                    flag = flag + 1
            while m > M:
                if flag == tar:
                    return tmp
                tmp = nums1[M]
                M = M + 1
                flag = flag + 1
            while n > N:
                if flag == tar:
                    return tmp
                tmp = nums2[N]
                N = N + 1
                flag = flag + 1
            return tmp

        def find_float(nums1, nums2, tar):
            # print("find_float")
            # print(nums1, nums2, tar)
            list_new = []
            flag = 0
            tmp = -1
            M = N = 0
            while m > M and n > N:
                if flag == tar + 1:
                    return list_new[-2], tmp
                if nums1[M] < nums2[N]:
                    tmp = nums1[M]
                    list_new.append(tmp)
                    M = M + 1
                    flag = flag + 1
                else:
                    tmp = nums2[N]
                    list_new.append(tmp)
                    N = N + 1
                    flag = flag + 1
            while m > M:
                if flag == tar + 1:
                    return list_new[-2], tmp
                tmp = nums1[M]
                list_new.append(tmp)
                M = M + 1
                flag = flag + 1
            while n > N:
                if flag == tar + 1:
                    return list_new[-2], tmp
                tmp = nums2[N]
                list_new.append(tmp)
                N = N + 1
                flag = flag + 1
            if flag == tar + 1:
                print(list_new)
                return list_new[-2], tmp
        if (m + n + 1) % 2 == 0:
            return find_int(nums1, nums2, int(median))
        else:
            a, b = (find_float(nums1, nums2, int(median)))
            return (a + b) / 2


solution = Solution()
nums1 = [1,1,3,3]
nums2 = [1,1,3,3]
print(solution.findMedianSortedArrays(nums1, nums2))