Median of Two Sorted Arrays

leetcode4

如题,两排序数组中找到中值,其中非奇情况,取两中值均值。
解法1:合并,排序,O(m*n)
解法2:只适用于此题情况,排序(更优解)。O(m+n),遍历两数组和,从小到达插入数组(理解为如题情况,模拟排序)。直到取到中值

class Solution:
    def findMedianSortedArrays(self, nums1, nums2):
        """
        :type nums1: List[int]
        :type nums2: List[int]
        :rtype: float
        """
        sumLen1 = len(nums1)
        sumLen2 = len(nums2)
        sumLen = sumLen1 + sumLen2
        midNum = sumLen / 2
        var1 = 0
        var2 = 0
        isMid = True
        if sumLen % 2 == 0:
            isMid = False
        tmpNum = 0
        sumNum = 0
        # tmpArr = {}
        for var in range(sumLen):
            if var1 != sumLen1:
                tmpNum = nums2[var2]
                # tmpArr[var] = tmpNum
                var2 = var2 + 1
            elif var2 != sumLen2:
                    tmpNum = nums1[var1]
                    # tmpArr[var] = tmpNum
                    var1 = var1 + 1
            else:
                if nums1[var1] != nums2[var2]:
                    tmpNum = nums1[var1]
                    # tmpArr[var] = tmpNum
                    var1 = var1 + 1
                else:
                    tmpNum = nums2[var2]
                    # tmpArr[var] = tmpNum
                    var2 = var2 + 1
            if isMid:
                if var + 1 == midNum:
                    sumNum = tmpNum
                    break
            elif not isMid:
                if var + 1 == midNum:
                    sumNum = sumNum + tmpNum
                if var == midNum:
                    sumNum = sumNum + tmpNum
                    sumNum = sumNum / 2
                    break
        return sumNum

bo-jwolf

一级美术,二级策划,三级程序

留下你的评论

*评论支持代码高亮<pre class="prettyprint linenums">代码</pre>

相关推荐