Leetcode题库——4.寻找两个有序数组的中位数

@author: ZZQ

@software: PyCharm

@file: findMedianSortedArrays.py

@time: 2018/10/10 19:24

说明：给定两个大小为 m 和 n 的有序数组 nums1 和 nums2 。请找出这两个有序数组的中位数。要求算法的时间复杂度为 O(log (m+n)) 。你可以假设 nums1 和 nums2 不同时为空。

示例 1: nums1 = [1, 3] nums2 = [2] 中位数是 2.0

示例 2: nums1 = [1, 2] nums2 = [3, 4] 中位数是 (2 + 3)/2 = 2.5

思路：空间换时间。首先判断合并后的数组奇偶，然后开辟新的空间l3来存放合并后的数据元素，存放到中位种停止，l3的最后一个元素就是中位数。

或者，用两个指针来存放中位数和中位数上一个元素的值，不断向前直至找到中位数。

class Solution(object):

    def findMedianSortedArrays(self, nums1, nums2):

        """

        :type nums1: List[int]

        :type nums2: List[int]

        :rtype: float

        """

        n = len(nums1)

        m = len(nums2)

        if (n+m) % 2 == 0:

            flag = True

        else:

            flag = False

        middle_index = (n + m) / 2 + 1

        nums1_index, nums2_index = 0, 0

        l3 = []

        while nums1_index < n and nums2_index < m:

            if nums1[nums1_index] > nums2[nums2_index]:

                l3.append(nums2[nums2_index])

                nums2_index += 1

            else:

                l3.append(nums1[nums1_index])

                nums1_index += 1

            if len(l3) == middle_index:

                break

        while nums1_index < n and nums2_index == m:

            if len(l3) == middle_index:

                break

            l3.append(nums1[nums1_index])

            nums1_index += 1

            if len(l3) == middle_index:

                break

        while nums2_index < m and nums1_index == n:

            if len(l3) == middle_index:

                break

            l3.append(nums2[nums2_index])

            nums2_index += 1

        if flag:

            middle_value = (l3[len(l3)-2] + l3[len(l3)-1])/2.0

        else:

            middle_value = l3[len(l3)-1]

        return middle_value

巴特西

Leetcode题库——4.寻找两个有序数组的中位数

最新文章

热门文章