Java教程

4. 寻找两个正序数组的中位数

本文主要是介绍4. 寻找两个正序数组的中位数,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

给定两个大小分别为 m 和 n 的正序(从小到大)数组 nums1 和 nums2。请你找出并返回这两个正序数组的 中位数 。

算法的时间复杂度应该为 O(log (m+n))

 

nums2 = [1,]
nums1 = [54,78,90,]

def test(nums):
    lengh = len(nums)
    if lengh % 2 == 0:
        index = [lengh / 2 - 1, lengh / 2]
    else:
        index = [lengh // 2]
    if len(index) == 2:
        # print(index)
        print(nums[int(index[0])], nums[int(index[1])])
    else:
        print(nums[int(index[0])])


if not nums2 or not nums1:
    if nums1:
        test(nums1)
    else:
        test(nums2)
else:
    lengh = len(nums1) + len(nums2)
    index = []
    if lengh == 1:
        index.append(0)
    elif lengh % 2 != 0:
        index.append((lengh - 1) // 2)
    else:
        index.append(lengh // 2 - 1)
        index.append(lengh // 2)

    result = []
    for it in range(index[-1] + 1):
        if nums1 and nums2:
            if nums1[0] > nums2[0]:
                result.append(nums2.pop(0))
        else:
            result.append(nums1.pop(0))

    print(result)
    if len(index) == 1:
        print(result[-1])
    else:
        print(result[-1] / 2 + result[-2] / 2)

 

这篇关于4. 寻找两个正序数组的中位数的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!