LeetCode:寻找两个正序数组的中位数

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

原题链接:https://leetcode-cn.com/problems/median-of-two-sorted-arrays/

解法一:代码简洁,但用了内置排序函数。
def findMedianSortedArrays(nums1, nums2):
    # 判空
    if not nums1 and not nums2:
        return 0
    # 一方为空
    elif (not nums1 and nums2) or (not nums2 and nums1):
        nums = nums1 or nums2
    # 非空
    else:
        nums = nums1 + nums2
        nums.sort()
    if len(nums) % 2 != 0:
        mid = int((len(nums) - 1) / 2)
        return nums[mid]
    else:
        right = int((len(nums) / 2))
        left = int(right - 1)
        return (nums[left] + nums[right]) / 2

解法二:真正面试中,考官往往不许我们使用任何内置排序函数,所以只能自己手写排序!
以下的排序不是通用排序方法,而是根据题目--正序(从小到大)数组写的一个排序,仅供参考。
def findMedianSortedArrays(nums1, nums2):
    # 判空
    if not nums1 and not nums2:
        return 0
    # 一方为空
    elif (not nums1 and nums2) or (not nums2 and nums1):
        new_nums = nums1 or nums2
    # 非空
    else:
        # 不使用内置排序函数,自己手写排序
        import copy
        len1, len2 = len(nums1), len(nums2)
        longer_nums = nums1 if len1 > len2 else nums2
        short_nums = nums2 if len1 > len2 else nums1
        # 此处要进行深拷贝,否则后面 new_nums 插入元素时,longer_nums 也会同步变化
        new_nums = copy.deepcopy(nums1) if len1 > len2 else copy.deepcopy(nums2)
        count = 0
        for idx, num in enumerate(longer_nums):
            while count < len(short_nums):
                if short_nums[count] > num:
                    if idx == len(longer_nums) - 1:
                        new_nums.extend(short_nums[count:])
                    break
                else:
                    # idx + count :第二个往后的元素在插入时,除了idx下标位,还因为前面元素的插入额外移动了count位
                    new_nums.insert(idx + count, short_nums[count])
                    count += 1
            if idx == len(longer_nums) - 1:
                break
    if len(new_nums) % 2 != 0:
        mid = int((len(new_nums) - 1) / 2)
        return new_nums[mid]
    else:
        right = int((len(new_nums) / 2))
        left = int(right - 1)
        return (new_nums[left] + new_nums[right]) / 2
     

LeetCode:寻找两个正序数组的中位数

上一篇:SpringBoot 如何生成接口文档


下一篇:数据结构与算法——栈(二)【使用栈来实现综合计算器-中缀表达式】