findMedianSortedArrays

题目

给定两个大小为 m 和 n 的有序数组 nums1 和 nums2。

请你找出这两个有序数组的中位数,并且要求算法的时间复杂度为 O(log(m + n))。

你可以假设 nums1 和 nums2 不会同时为空。

DEMO

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

则中位数是 2.0


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

则中位数是 (2 + 3)/2 = 2.5

解法

合并计算长度取值

nums1nums2合并为一个new_nums,计算新数组的长度,然后再直接取值是中间的数还是中间两个数的平均数。

  • LeetCode结果116ms/11.9MB
  • 复杂度达标:否
def findMedianSortedArrays(nums1, nums2):
    new_list = nums1 + nums2
    length = len(new_list)
    new_list.sort()
    if length%2:
        if length == 1:
            return new_list[0]
        return new_list[length//2]
    else:
        return (new_list[length/2-1]+new_list[length/2])/2.0

分别取中值(二分法)

步骤:

  1. nums1的中值,nums2的中值对比
  2. 将较小的一方包含中值在内的数移除,并记录计数器del_nums_count
  3. 对比del_nums_count的大小和中位数的索引k(索引固定为num1+nums2长度的中间值或中间两个值),如果del_nums_count的长度已经大于了k,则需要在此次将要移除的子数组中进行取索引定位;反之,继续执行2
def findMedianSortArrays(nums1, nums2):
    nums1_length = len(nums1)
    nums2_length = len(nums2)

    # 计算中位数k的索引        
    if (nums1_length+nums2_length)%2:
        k = (nums1_length+nums2_length)//2
    else:
        k = (nums1_length+num2_length)/2+0.5

    remove_nums_count = 0
    while True:
        if nums1[nums1_length//2] >= nums2[nums2_length//2]:
            remove_nums = num2[:num2_length//2+1]
             if nums2_length//2+remove_nums_count >= k:
                if k%2:
                    k_value = remove_nums[k-remove_nums_count]
                else:
                    k_value = (remove_nums[k-remove_nums_count-1]+remove_nums[k-remove_nums_count])/2.0
                break
            else:
                remove_count = num2_length//2+1
                nums2_length //= 2
        else:
            remove_nums = num1[:num1_length//2+1]
            if nums1_length//2+remove_nums_count >= k:
                if k%2:
                    k_value = remove_nums[k-remove_nums_count]
                else:
                    k_value = (remove_nums[k-remove_nums_count-1]+remove_nums[k-remove_nums_count])/2.0
                break
            else:
                remove_count = num1_length//2+1
                nums1_length //= 2



  转载请注明: Tomorrow findMedianSortedArrays

 上一篇
python类反射 python类反射
起因 最近一直在写数据构造器,所有的虚假数据均调用的是一个Methor类,需要用到类反射。 采取的做法方法一 为了方便,采取了eval()将组合成的方法名字符串运行成函数,刚开始很正常,但是一看速度,心态炸了啊!!!!!平均需要0.03s
2019-06-24
下一篇 
lengthOfLongestSubstring lengthOfLongestSubstring
题目 给定一个字符串,请你找出其中不含有重复字符的 最长子串 的长度。 DEMO 输入: “abcabcbb”输出: 3解释: 因为无重复字符的最长子串是 “abc”,所以其长度为 3。 输入: “bbbbb”输出: 1解释: 因为无重
2019-06-03
  目录