最近再刷leetcode,除了鏈表之外的都用python 實現(xiàn),貼出一些代碼,希望指正.

問題描述:

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)).
找兩個排序好的數(shù)組的中位數(shù).

樣例輸入:

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

The median is 2.0

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

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

算法思想:

我再這里對兩個數(shù)組的len和是奇數(shù)還是偶數(shù)做了分開對待.

1. 如果兩個數(shù)組len和是奇數(shù).
   對兩個數(shù)組進(jìn)行從小到大遍歷,同時遍歷,當(dāng)遍歷到(length+1)/2輸出結(jié)果,不過需要注意的是,兩個數(shù)組的長度不同,可能出現(xiàn)某個遍歷完了,某個還沒有完的情況,所以在同時遍歷完成之后還需要,對沒有完成的進(jìn)行遍歷.
2. 對于兩個數(shù)組的len和是偶數(shù)的情況.
   如果兩個數(shù)組的len和是偶數(shù),那就說明中位數(shù),是最中間兩個和的一半,這時就需要對上一個結(jié)果進(jìn)行存儲,遍歷時,需要找到(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))