欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

Median of Two Sorted Arrays (leetcode 4)

程序员文章站 2022-03-23 17:32:25
...

Version 1:

本题题意是在两个有序数组中找中间数,n 和 m 分别是两个数组nums1 和nums2 的长度,若n+m 是奇数,则中间数为中位数,若是偶数,则中间数就是中间两个数值的平均数。虽然题目要求时间复杂度为Median of Two Sorted Arrays (leetcode 4),但是脑海最先想到的第一个版本的做法就是对前一半进行归并排序,找到中间的数,进行返回,后面一半不做处理,时间复杂度为Median of Two Sorted Arrays (leetcode 4),代码和结果如下:


class Solution:
    def findMedianSortedArrays(self, nums1, nums2):
        """
        :type nums1: List[int]
        :type nums2: List[int]
        :rtype: float
        """

        # use the merge method to sort the top (m+n)/2 element
        n = len(nums1)
        m = len(nums2) 

        # deal with the situation : one list is empty
        # the number of nums1 is even and nums2 is empty
        if m == 0 and n%2 == 0:
        	return (nums1[int((n-1)/2)] + nums1[int(n/2)])/2
        # the number of nums1 is odd and nums2 is empty
        if m == 0:
        	return nums1[int(n/2)]
        # the number of nums2 is even and nums1 is empty
        if n == 0 and m%2 == 0:
        	return (nums2[int((m-1)/2)] + nums2[int(m/2)])/2
        # the number of nums2 is odd and nums1 is empty
        if n == 0:
        	return nums2[int(m/2)]


        cur = 0
        cur_num = 0
        i = -1
        j = -1
        while cur <= int((n + m - 1)/2):
        	# nums1 and nums2 both have element
        	if (i+1) < n and (j+1) <m:
        		if nums1[i+1] > nums2[j+1]:
        			j += 1
        			cur_num = nums2[j]
        		else:
        			i += 1
        			cur_num = nums1[i]
        	# just nums1 have element
        	elif (i+1) < n:
        		i += 1
        		cur_num = nums1[i]
        	# just nums2 have element
        	else:
        		j += 1
        		cur_num = nums2[j]
        	cur += 1
        next_num = 0
        # nums1 and nums2 both have element
        if (i+1) < n and (j+1) <m:
        	next_num = min(nums1[i+1],nums2[j+1])
        # just nums1 have element
        elif (i+1) < n:
        	next_num = nums1[i+1]
        # just nums2 have element
        else:
        	next_num = nums2[j+1]
        if (n + m)%2 == 0:
        	return (cur_num + next_num) / 2
        else: 
        	return cur_num

Median of Two Sorted Arrays (leetcode 4)

符合要求的时间复杂度的算法暂时肝不出来,周末再看看,毕竟今儿脑子有点小忧伤。毕竟耗时太长也不是件好事,切换下一关先。顺便考虑学习下已经解题的前辈的优秀方法。